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 of 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.
You can use the following BibTeX citations to cite our book and related paper:
@book{hlx2019community,
title = {Community Search over Big Graphs},
author = {Huang, Xin and Lakshmanan, Laks VS and Xu, Jianliang},
year = {2019},
publisher = {Morgan \& Claypool Publishers}
}
@inproceedings{hlx2017community,
title = {Community search over big graphs: Models, algorithms, and opportunities},
author = {Huang, Xin and Lakshmanan, Laks VS and Xu, Jianliang},
booktitle = {Proceedings of the 33rd IEEE International Conference on Data Engineering (ICDE)},
pages = {1451--1454},
year = {2017}
}
If your papers on community search don't appear below, please kindly email us your paper titles.
Cohesive Community Search
L. Yuan, L. Qin, W. Zhang, L. Chang, and J. Yang. Index-Based Densest Clique Percolation Community Search in Networks. TKDE, 30(5): 922-935, 2018.
F. Zhang, L. Yuan, Y. Zhang, L. Qin, X. Lin, and A. Zhou. Discovering strong communities with user engagement and tie strength. In DASFAA, pages 425–441, 2018.
Y. Fang, Z. Wang, R. Cheng, H. Wang, and J. Hu. Effective and Efficient Community Search over Large Directed Graphs. TKDE, 2018.
E. Akbas and P. Zhao. Truss-based community search: a truss-equivalence based indexing approach. PVLDB, 10(11):1298–1309, 2017.
Y. Bian, J. Ni, W. Cheng, and X. Zhang. Many heads are better than one: Local community detection by the multi-walker chain. In ICDM, pages 21–30, 2017.
Y. Bian, Y. Yan, W. Cheng, W. Wang, D. Luo, and X. Zhang. On multi-query local community detection. In ICDM, pages 9–18, 2018.
L. Cai, T. Meng, T. He, L. Chen, and Z. Deng. K-hop community search based on local distance dynamics. In International Conference on Neural Information Processing, pages 24–34, 2017.
J. Hu, X. Wu, R. Cheng, S. Luo, and Y. Fang. On minimal steiner maximum-connected subgraph queries. TKDE, 29(11):2455–2469, 2017.
A. M. Katunka, C. Yan, K. B. Serge, and Z. Zhang. K-truss based top-communities search in large graphs. In International Conference on Advanced Cloud and Big Data, pages 244–249. IEEE, 2017.
L.-Y. Kuo, C.-K. Chou, and M.-S. Chen. Query-oriented graph clustering. In PAKDD, pages 749–761, 2017.
Y. Wang, X. Jian, Z. Yang, and J. Li. Query optimal k-plex based community in graphs. Data Science and Engineering, 2(4):257–273, 2017.
P. Lee and L. V. Lakshmanan. Query-driven maximum quasi-clique search. In SDM, pages 522–530, 2016.
J. Shan, D. Shen, T. Nie, Y. Kou, and G. Yu. Searching overlapping communities for group query. World Wide Web, 19(6):1179–1202, 2016.
J. Hu, X. Wu, R. Cheng, S. Luo, and Y. Fang. Querying Minimal Steiner Maximum-Connected Subgraphs in Large Graphs. In CIKM, 2016.
X. Huang, L. V. Lakshmanan, J. X. Yu, and H. Cheng. Approximate closest community search in networks. PVLDB, 9(4):276–287, 2015.
Y. Wu, R. Jin, J. Li, and X. Zhang. Robust local community detection: On free rider effect and its elimination. PVLDB, 8(7), 2015.
L. Chang, X. Lin, L. Qin, J. X. Yu, and W. Zhang. Index-based optimal algorithms for computing steiner components with maximum connectivity. In SIGMOD, pages 459–474, 2015.
N. Barbieri, F. Bonchi, E. Galimberti, and F. Gullo. Efficient and effective community search. DMKD, 29(5):1406–1433, 2015.
N. Ruchansky, F. Bonchi, D. García-Soriano, F. Gullo, and N. Kourtellis. The minimum wiener connector problem. In SIGMOD, pages 1587–1602, 2015.
J. Shan, D. Shen, T. Nie, Y. Kou, and G. Yu. An efficient approach of overlapping communities search. In DASFAA, pages 374–388, 2015.
X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying k-truss community in large and dynamic graphs. In SIGMOD, pages 1311–1322, 2014.
W. Cui, Y. Xiao, H. Wang, and W. Wang. Local search of communities in large graphs. In SIGMOD, pages 991–1002, 2014.
W. Cui, Y. Xiao, H. Wang, Y. Lu, and W. Wang. Online search of overlapping communities. In SIGMOD, pages 277–288, 2013.
M. Sozio and A. Gionis. The community-search problem and how to plan a successful cocktail party. In KDD, pages 939–948, 2010.
L. Qin, J. X. Yu, L. Chang, and Y. Tao. Querying communities in relational databases. In ICDE, pages 724–735, 2009.
Attributed Community Search
Z. Zhang, X. Huang, J. Xu, B. Choi, and Z. Shang. Keyword centric community search. In ICDE, pages 422–433, 2019.
L. Chen, C. Liu, K. Liao, J. Li, and R. Zhou. Contextual Community Search Over Large Social Networks. In ICDE, pages 88-99, 2019.
Y. Chen, Y. Fang, R. Cheng, Y. Li, X. Chen, and J. Zhang. Exploring Communities in Large Profiled Graphs. TKDE, 2019.
R.-H. Li, Q. Dai, L. Qin, G. Wang, X. Xiao, J. X. Yu, and S. Qiao. Efficient Signed Clique Search in Signed Networks. In ICDE, pages 245-256, 2018.
R.-H. Li, J. Su, L. Qin, J. X. Yu, and Q. Dai. Persistent Community Search in Temporal Networks. In ICDE, pages 797-808, 2018.
J. Xu, X. Fu, L. Tu, M. Luo, M. Xu, and N. Zheng. Personalized top-n influential community search over large social networks. In APWeb-WAIM, pages 105–120, 2018.
F. Bi, L. Chang, X. Lin, and W. Zhang. An optimal and progressive approach to online search of top-k influential communities. PVLDB, 11(9):1056–1068, 2018.
R.-H. Li, L. Qin, F. Ye, J. X. Yu, X. Xiao, N. Xiao, and Z. Zheng. Skyline community search in multi-valued networks. In SIGMOD, pages 457–472, 2018.
X. Huang and L. V. Lakshmanan. Attribute-driven community search. PVLDB, 10(9):949–960, 2017.
J. Li, X. Wang, K. Deng, X. Yang, T. Sellis, and J. X. Yu. Most influential community search over large social networks. In ICDE, pages 871–882, 2017.
J. Shang, C. Wang, C. Wang, G. Guo, and J. Qian. An attribute-based community search method with graph refining. The Journal of Supercomputing, pages 1–28, 2017.
Z. Wang, Y. Yuan, G. Wang, H. Qin, and Y. Ma. An effective method for community search in large directed attributed graphs. In International Conference on Mobile Ad-Hoc and Sensor Networks, pages 237–251, 2017.
D. Zheng, J. Liu, R.-H. Li, C. Aslay, Y.-C. Chen, and X. Huang. Querying intimate-core groups in weighted graphs. In ICSC, pages 156–163, 2017.
Z. Zheng, F. Ye, R.-H. Li, G. Ling, and T. Jin. Finding weighted k-truss communities in large networks. Information Sciences, 417:344–360, 2017.
Y. Fang, R. Cheng, Y. Chen, S. Luo, and J. Hu. Effective and Efficient Attributed Community Search. The VLDB Journal, 2017.
R.-H. Li, L. Qin, J. X. Yu, and R. Mao. Finding influential communities in massive networks. The VLDB Journal, 26(6): 751-776, 2017.
Y. Fang, R. Cheng, S. Luo, and J. Hu. Effective community search for large attributed graphs. PVLDB, 9(12):1233–1244, 2016.
R.-H. Li, L. Qin, J. X. Yu, and R. Mao. Influential community search in large networks. PVLDB, 8(5), 2015.
Social Circle Analysis
M. Wang, W. Zuo, and Y. Wang. An improved density peaks-based clustering method for social circle discovery in social networks. Neurocomputing, 179:219–227, 2016.
X. Huang, H. Cheng, R.-H. Li, L. Qin, and J. X. Yu. Top-k structural diversity search in large networks. The VLDB Journal, 24(3):319–343, 2015.
Y. Wang and L. Gao. An edge-based clustering algorithm to detect social circles in ego networks. Journal of computers, 8(10):2575–2582, 2013.
X. Huang, H. Cheng, R.-H. Li, L. Qin, and J. X. Yu. Top-k structural diversity search in large networks. PVLDB, 6(13):1618–1629, 2013.
J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. PNAS, 109(16):5962–5966, 2012.
J. Leskovec and J. J. Mcauley. Learning to discover social circles in ego networks. In NIPS, pages 539–547, 2012.
N. Wang, J. Zhang, K.-L. Tan, and A. K. H. Tung. On triangulation-based dense neighborhood graphs discovery. PVLDB, 4(2):58–68, 2010.
Geo-Social Group Search
B. Ghosh, M. E. Ali, F. M. Choudhury, S. H. Apon, T. Sellis, J. Li.
The Flexible Socio Spatial Group Queries. PVLDB 12(2): 99-111, 2018.
Y. Fang, Z. Wang, R. Cheng, X. Li, S. Luo, J. Hu, and X. Chen. On spatial-aware community search. TKDE, 2018.
L. Chen, C. Liu, R. Zhou, J. Li, X. Yang, and B. Wang. Maximum co-located community search in large scale social networks. PVLDB, 11(9), 2018.
Y. Fang, R. Cheng, X. Li, S. Luo, and J. Hu. Effective community search over large spatial graphs. PVLDB, 10(6):709–720, 2017.
Q. Zhu, H. Hu, C. Xu, J. Xu, and W.-C. Lee. Geo-social group queries with minimum acquaintance constraints. The VLDB Journal, 26(5):709–727, 2017.
Y. Li, R. Chen, J. Xu, Q. Huang, H. Hu, and B. Choi. Geo-social k-cover group queries for collaborative spatial computing. In ICDE, pages 1510–1511, 2016.
Y. Li, R. Chen, J. Xu, Q. Huang, H. Hu, and B. Choi. Geo-social k-cover group queries for collaborative spatial computing. TKDE, 27(10):2729–2742, 2015.
R. Andersen and K. Chellapilla. Finding dense subgraphs with size bounds. In International Workshop on Algorithms and Models for the Web-Graph, pages 25–37, 2009.
Graph Decompostion (via Core/Truss/ECC)
L. Chang and L. Qin. Cohesive Subgraph Computation over Large Sparse Graphs: Algorithms, Data Structures, and Programming Techniques. Springer, 2018.
Z. Zou and R. Zhu. Truss decomposition of uncertain graphs. Knowledge and Information Systems, 50(1):197–230, 2017.
X. Huang, W. Lu, and L. V. S. Lakshmanan. Truss decomposition of probabilistic graphs: Semantics and algorithms. In SIGMOD, pages 77–90, 2016.
D. Wen, L. Qin, Y. Zhang, X. Lin, and J. X. Yu. I/O efficient core graph decomposition at web scale. In ICDE, pages 133–144, 2016.
F. Bonchi, F. Gullo, A. Kaltenbrunner, and Y. Volkovich. Core decomposition of uncertain graphs. In KDD, pages 1316–1325, 2014.
L. Chang, J. X. Yu, L. Qin, X. Lin, C. Liu, and W. Liang. Efficiently computing k-edge connected components via graph decomposition. In SIGMOD, pages 205–216, 2013.
J. Wang and J. Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812–823, 2012.
J. Cheng, Y. Ke, S. Chu, and M. T. Özsu. Efficient core decomposition in massive networks. In ICDE, pages 51–62, 2011.
J. Cohen. Trusses: Cohesive subgraphs for social network analysis. Technical report, National Security Agency, 2008.
Survey, Demo, and Tutorial
[Survey] Y. Fang, X. Huang, L. Qin, Y. Zhang, W. Zhang, R. Cheng, and X. Lin. A Survey of Community Search Over Big Graphs. The VLDB Journal, 2019.
[Demo] Y. Jiang, X. Huang, H. Cheng, and J. X. Yu. Vizcs: Online searching and visualizing communities in dynamic graphs. In ICDE, 2018.
[Demo] Y. Fang, R. Cheng, S. Luo, J. Hu, and K. Huang. C-explorer: browsing communities in large graphs. PVLDB, 10(12):1885–1888, 2017.
[Tutorial] X. Huang, L. V. Lakshmanan, and J. Xu. Community search over big graphs: Models, algorithms, and opportunities. In ICDE, pages 1451–1454. IEEE, 2017.
Contact Us :