Cohesive Subgraph Search Over Large Heterogeneous Information Networks

✍ Scribed by Yixiang Fang, Kai Wang, Xuemin Lin, Wenjie Zhang

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 86
• Series: SpringerBriefs in Computer Science
• Category: Library

✦ Synopsis

This SpringerBrief provides the first systematic review of the existing works of cohesive subgraph search (CSS) over large heterogeneous information networks (HINs). It also covers the research breakthroughs of this area, including models, algorithms and comparison studies in recent years. This SpringerBrief offers a list of promising future research directions of performing CSS over large HINs.

The authors first classify the existing works of CSS over HINs according to the classic cohesiveness metrics such as core, truss, clique, connectivity, density, etc., and then extensively review the specific models and their corresponding search solutions in each group. Note that since the bipartite network is a special case of HINs, all the models developed for general HINs can be directly applied to bipartite networks, but the models customized for bipartite networks may not be easily extended for other general HINs due to their restricted settings. The authors also analyze and compare these cohesive subgraph models (CSMs) and solutions systematically. Specifically, the authors compare different groups of CSMs and analyze both their similarities and differences, from multiple perspectives such as cohesiveness constraints, shared properties, and computational efficiency. Then, for the CSMs in each group, the authors further analyze and compare their model properties and high-level algorithm ideas.

This SpringerBrief targets researchers, professors, engineers and graduate students, who are working in the areas of graph data management and graph mining. Undergraduate students who are majoring in computer science, databases, data and knowledge engineering, and data science will also want to read this SpringerBrief.

✦ Table of Contents

Preface
Acknowledgments
Contents
About the Authors
Acronyms
1 Introduction
1.1 Background
1.2 Challenges of CSS Over Large HINs
1.3 Classification of Existing Works of CSS Over HINs
2 Preliminaries
2.1 Data Models of HINs and Bipartite Networks
2.2 CSMs on Homogeneous Networks
3 CSS on Bipartite Networks
3.1 Core-Based CSMs and Solutions
3.1.1 The (α, β)-Core Model
3.1.2 The Generalized Two-Mode Core Model
3.1.3 The Fractional k-Core Model
3.1.4 The τ-Strengthened (α, β)-Core Model
3.2 Truss-Based CSMs and Solutions
3.2.1 The k-Bitruss Model
3.2.2 The k-Tip Model
3.2.3 The Quasi-Truss Model
3.3 Clique-Based CSMs and Solutions
3.3.1 The Maximal Biclique Model
3.3.2 The Maximum Vertex Biclique Model
3.3.3 The Maximum Edge Biclique Model
3.3.4 The Maximum Balanced Biclique Model
3.3.5 The Quasi-Biclique Model
3.4 Connectivity-Based CSMs and Solutions
3.5 Density-Based CSMs and Solutions
3.5.1 The Densest Subgraph Model
3.5.2 The (p, q)-Biclique Densest Subgraph Model
3.6 Conclusions
4 CSS on Other General HINs
4.1 Some Key Concepts on HINs
4.2 Core-Based CSMs and Solutions
4.2.1 The (k, P)-Core Models
4.2.2 The r-Com Model
4.2.3 The h-Structure Model
4.2.4 The (a1, @汥瑀瑯步渠, ak)-Core Model
4.2.5 The Multi-Layer Core Model
4.3 Truss-Based CSMs and Solutions
4.3.1 The (k, P)-Btruss and (k, P)-Ctruss Models
4.3.2 The (b1, @汥瑀瑯步渠, bk)-Truss Model
4.4 Clique-Based CSMs and Solutions
4.4.1 The Maximal Motif-Clique Model
4.4.2 The ABCOutlier-Clique Model
4.4.3 The k-Partite Clique Model
4.4.4 Multi-Layer Quasi-Clique Models
4.5 Density-Based CSMs and Solutions
4.6 Other CSMs and Solutions
4.7 Conclusions
5 Comparison Analysis
5.1 Bipartite Networks
5.1.1 Comparison of Different Groups of CSMs
5.1.2 Comparison of Different Core-Based Models
5.1.3 Comparison of Different Truss-Based Models
5.1.3.1 Comparison of Different Clique-Based Models
5.2 Other General HINs
5.2.1 Comparison of Different Groups of CSMs
5.2.2 Comparison of Different Core-Based Models
5.2.3 Comparison of Different Truss-Based Models
5.2.4 Comparison of Different Clique-Based Models
6 Related Work on CSMs and Solutions
6.1 CSS on Homogeneous Networks
6.1.1 Core-Based CSS
6.1.2 Truss-Based CSS
6.1.3 Clique-Based CSS
6.1.4 Connectivity-Based CSS
6.1.5 Density-Based CSS
6.2 HIN Clustering
6.2.1 Bipartite Networks
6.2.2 Other General HINs
6.2.3 Comparison with the Earlier Version
7 Future Work and Conclusion
7.1 Novel Application-Driven CSMs
7.2 Efficient Search Algorithms on Big HINs
7.3 Parameters Optimization
7.4 An Online Repository for Collecting HIN Datasets, Tools, and Algorithm Codes
7.5 Conclusion
References