Community Search over Big Graphs

Description

Communities serve as basic structural building blocks for understanding the organization of many real-world networks, including social, biological, collaboration, and communication networks. Recently, community search over graphs has attracted significantly increasing attention, from small, simple, and static graphs to big, evolving, attributed, and location-based graphs. In this book, we first review the basic concepts of networks, communities, and various kinds of dense subgraph models. We then survey the state of the art in community search techniques on various kinds of networks across different application areas. Specifically, we discuss cohesive community search, attributed community search, social circle discovery, and geo-social group search. We highlight the challenges posed by different community search problems. We present their motivations, principles, methodologies, algorithms, and applications, and provide a comprehensive comparison of the existing techniques. This book finally concludes by listing publicly available real-world datasets and useful tools for facilitating further research, and by offering further readings and future directions of research in this important and growing area. Acknowledgments Introduction Graphs and Communities Graphs Communities Community Search Community Search Problem A Comparison with Community Detection Applications Datasets and Tools Prerequisite and Target Reader Outline of the Book Cohesive Subgraphs Community Search and Cohesive Subgraphs Notations and Notions Graphs and Subgraphs Degree and Neighbors Path, Cycle, Connectivity, and Diameter Classical Dense Subgraphs Clique and Quasi-Clique k-DBDSG, k-clan, k-club, and k-plex k-core and k-truss k-core k-truss More Dense Subgraphs Densest Subgraphs k-ecc and k-vcc Other Dense Subgraphs Summary Cohesive Community Search Quasi-Clique Community Models Clique-Based Community Detection Quasi-Clique-Based Community Search Core-Based Community Models Maximum-Core Community Search Minimum-Sized k-Core Community Search Influential Community Search Comparison of Various k-core Community Models Truss-Based Community Models Triangle-Connected Truss Community Search Closest Truss Community Search Query-Biased Densest Community Model Notions and Notations Problem Formulation Algorithms Summary Attributed Community Search Introduction Attributed Networks Limitations of Cohesive Community Search without Query Attributes Desiderata of Good Attributed Communities K-Core-Based Attribute Community Model Problem Formulation Basic Query Processing Algorithm CLTree-Index-Based Query Processing Algorithms K-Truss-Based Attribute Community Model (k, d)-Truss Attribute Score Function Attributed Truss Community Model ATindex-Based Greedy Algorithm Summary Case Study on the DBLP Network Case Study on the PPI Network with Ground-Truth Communities Comparison between ACC and ATC Models Comparison with Other Related Works Social Circle Analysis Ego-Networks Structural Diversity Search Motivations Problem Formulation A Simple Degree-Based Approach A Novel Top-k Search Framework Case Studies Learning to Discover Social Circles Attributed Community Search and Social Circle Discovery Problem Formulation A Generative Model for Social Circle Discovery Geo-Social Group Search Geo-Social Group Search Proximity-Based Geo-Social Group Search Problem Statement R-Tree-Based Query Processing Social-Aware R-Tree SaR-Tree-Based Query Processing Geo-Social k-Cover Group Search Problem Statement Algorithms Geo-Social Group Search Based on Minimum Covering Circle Problem Statement Algorithms Datasets and Tools Real-World Datasets Networks with Ground-Truth Communities Attributed Graphs with Ground-Truth Communities Ego-Networks with Ground-Truth Social Circles Geo-Social Networks Public-Private Collaboration Networks Query Generation and Evaluation Query Generation Evaluation Metrics Software and Demo Systems Suggestions on Dense Subgraph Selection for Community Models Further Readings and Future Directions Further Readings Clique-Based Community Search Core-Based Community Search Truss-Based Community Search Plex-Based Community Search Others Future Directions and Open Problems Querying Communities on Heterogeneous Information Networks Scalable Algorithms for Big Graphs Public-Private Social Networks Community Search on Probabilistic Graphs Applications and Case Studies Conclusions Bibliography Authors' Biographies