Community-Centric Mining of Large-Scale Dynamic Graphs

图无处不在，是来自网络、社会和知识网络、通信网络、交易网络和流行病学网络的许多真实世界数据的最自然的表示。它们正以前所未有的速度增长。例如，网络图谱由超过一万亿的网站组成，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.