Community-Centric Mining of Large-Scale Dynamic Graphs

对于来自网络、社交和知识网络、通信网络、交易网络和流行病网络的许多现实世界的数据，图表是无处不在的、最自然的表示。它们正以前所未有的速度增长。例如，网络图由超过1万亿个网站组成，Facebook、Twitter和微博的社交图拥有数十亿用户，每个用户都有很多朋友/关注链接。因此，存储这样的图并回答查询、挖掘模式和产生洞察力变得非常具有挑战性。这些图表在其节点和边缘上还带有复杂和多样化的类型，可以表示人员、项目及其交互，从而形成真正的异质信息网络。此外，信息可能是不精确和不确定的，因此需要对数据进行概率推理。不仅迫切需要新的算法来处理这些复杂的图形数据集，而且必须从头开始解决可扩展性问题，以满足组织对工业强度图形分析的真正需求。我们研究的另一个核心维度是图形数据的高度动态特性。社会、网络、交易和流行病网络在不断发展，因此有必要相应地更新分析。本研究的目标是介绍在信息的异构性、动态性和不精确性的现实条件下管理大规模图形数据的方法和技术。我们的主要目标是在大型社交和网络图表上实现基本分析的可扩展性。我们对以下方面的分析特别感兴趣：(A)在社会和其他网络中发现社区，(B)在不同类型网络的社区中挖掘多样性，(C)挖掘和更新有影响力的社区，(D)促进良好信息的传播以及消除有害的错误信息。与其他作品不同，我们的目标是解决复杂的、大规模的图表，这些图表随着时间的推移不断演变。因此，我们的算法将是完全动态的，并解决了上述网络中存在的固有时间性。我们将解决原子和批处理类型的更新，每种更新都有自己的挑战和应用程序。我们预计，我们的研究将在社会网络利用、知识图谱分析、生物网络研究、流行病评估等众多应用中带来新的见解和效率。了解大型异质和动态图中的社区结构是为这些应用提供计算洞察力的探索的重要组成部分。我们希望我们的方法和结果为大量研究提供计算手段，使私营和公共部门的大小组织受益。

Graphs are ubiquitous and the most natural representation for many real world data coming from web, social, and knowledge networks, communication networks, transaction networks, and epidemiological networks. They are growing at an unprecedented rate. For instance, the web graph consists of more than a trillion websites, and the social graphs of Facebook, Twitter, and Weibo, have billions of users with many friend/follow connections per user. Consequently, storing such graphs and answering queries, mining patterns, and producing insights are becoming very challenging. These graphs also come with complex and diverse types on their nodes and edges which can represent people, items, and their interactions making for truly heterogeneous information networks. Furthermore, the information can be imprecise and uncertain, thus necessitating a probabilistic reasoning on the data. Not only is there a pressing need for new algorithms to handle these complex graph datasets, but scalability has to be addressed from the ground up to serve the real needs of organizations for industrial strength graph analytics. Another dimension that is central to our research is the highly dynamic nature of graph data. Social, web, transaction, and epidemiological networks are constantly evolving, thus necessitating that analytics be updated accordingly. Our goal in this research is to introduce methods and techniques to manage large-scale graph data under realistic conditions of heterogeneity, dynamicity, and impreciseness of information. Our main objective is to achieve scalability of fundamental analytics on big social and web graphs. We are particularly interested in analytics pertaining to (a) community discovery in social and other networks, (b) mining diversity in communities of heterogeneous networks, (c) mining and updating influential communities, (d) facilitation of the diffusion of good information as well as the removal of harmful misinformation. In contrast to other works, we aim at addressing complex, large scale graphs that continually evolve over time. As such, our algorithms will be fully dynamic and address the inherent temporality present in the aforementioned networks. We will address both atomic and batch type of updates, each with their own challenges and applications. We anticipate that our research will bring new insights and efficiency in a multitude of applications, such as social network utilization, knowledge graph analytics, biological network studies, epidemics evaluation, and so on. Understanding the structure of communities in large heterogeneous and dynamic graphs is an important part of the quest for providing computational insights to these applications. We expect our methods and results to provide the computational means for a large body of research benefiting large and small organizations in the private and public sector.