Community-Centric Mining of Large-Scale Dynamic Graphs

点击翻译按钮获取中文摘要

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.