Efficient multi-scale community search method based on spectral graph wavelet

Abstract

Community search is an important problem in network analysis, which has attracted much attention in recent years. As a query-oriented variant of community detection problem, community search starts with some given nodes, pays more attention to local network structures, and gets personalized resultant communities quickly. The existing community search method typically returns a single target community containing query nodes by default. This is a strict requirement and does not allow much flexibility. In many real-world applications, however, query nodes are expected to be located in multiple communities with different semantics. To address this limitation of existing methods, an efficient spectral-based Multi-Scale Community Search method (MSCS) is proposed, which can simultaneously identify the multi-scale target local communities to which query node belong. In MSCS, each node is equipped with a graph Fourier multiplier operator. The access of the graph Fourier multiplier operator helps nodes to obtain feature representations at various community scales. In addition, an efficient algorithm is proposed for avoiding the large number of matrix operations due to spectral methods. Comprehensive experimental evaluations on a variety of real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

Graphical abstract

Keywords

community search / multi-scale / spectral wavelets

References

[1] Fortunato S . Community detection in graphs. Physics Reports, 2010, 486( 3−5): 75–174

[2] Capriello A, Altinay L, Monti A . Exploring resource procurement for community−based event organization in social enterprises: evidence from Piedmont, Italy. Current Issues in Tourism, 2019, 22( 19): 2319–2322

[3] Li S, Song X, Lu H, Zeng L, Shi M, Liu F . Friend recommendation for cross marketing in online brand community based on intelligent attention allocation link prediction algorithm. Expert Systems with Applications, 2020, 139: 112839

[4] Fang Y, Huang X, Qin L, Zhang Y, Zhang W, Cheng R, Lin X . A survey of community search over big graphs. The VLDB Journal, 2020, 29( 1): 353–392

[5] Forouzandeh S, Rostami M, Berahmand K . A hybrid method for recommendation systems based on tourism with an evolutionary algorithm and topsis model. Fuzzy Information and Engineering, 2022, 14( 1): 26–50

[6] Li J, Ma H, Li Q, Li Z, Chang L. A two−stage community search method based on seed replacement and joint random walk. In: Proceedings of International Joint Conference on Neural Networks. 2021, 1–7

[7] Chang Y, Ma H, Chang L, Li Z . Community detection with attributed random walk via seed replacement. Frontiers of Computer Science, 2022, 16( 5): 165324

[8] Reichardt J, Bornholdt S . Statistical mechanics of community detection. Physical Review E, 2006, 74( 1): 016110

[9] Hammond D K, Vandergheynst P, Gribonval R . Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2011, 30( 2): 129–150

[10] Liu Q, Zhu Y, Zhao M, Huang X, Xu J, Gao Y. VAC: vertex−centric attributed community search. In: Proceedings of the 36th IEEE International Conference on Data Engineering. 2020, 937–948

[11] Yang Z, Li X, Zhang X, Luo W, Li K . K−truss community most favorites query based on top−t. World Wide Web, 2022, 25( 2): 949–969

[12] Tsourakakis C. The k−clique densest subgraph problem. In: Proceedings of the 24th International Conference on World wide Web. 2015, 1122–1132

[13] Meng S, Yang H, Liu X, Chen Z, Xuan J, Wu Y . Personalized influential community search in large networks: a K−ECC−based model. Discrete Dynamics in Nature and Society, 2021, 2021: 5363946

[14] Wei J, Ma H, Liu Y, Li Z, Li N . Hierarchical high−order co−clustering algorithm by maximizing modularity. International Journal of Machine Learning and Cybernetics, 2021, 12( 10): 2887–2898

[15] Li Q, Ma H, Li J, Li Z, Jiang Y. Incorporating user preference into multi−community and outliers search. In: Proceedings of International Joint Conference on Neural Networks. 2021, 1–8

[16] Li Q, Ma H, Li J, Li Z, Jiang Y . Searching target communities with outliers in attributed graph. Knowledge−Based Systems, 2022, 235: 107622

[17] Gao J, Chen J, Li Z, Zhang J . ICS−GNN: lightweight interactive community search via graph neural network. Proceedings of the VLDB Endowment, 2021, 14( 6): 1006–1018

[18] Jiang Y, Rong Y, Cheng H, Huang X, Zhao K, Huang J. Query driven-graph neural networks for community search: from non-attributed, attributed, to interactive attributed. 2021, arXiv preprint arXiv: 2104, 0358: 3

[19] Von Luxburg U . A tutorial on spectral clustering. Statistics and Computing, 2007, 17( 4): 395–416

[20] Newman M E J . Spectral methods for community detection and graph partitioning. Physical Review E, 2013, 88( 4): 042822

[21] Zhang S, Wang R S, Zhang X S . Identification of overlapping community structure in complex networks using fuzzy c−means clustering. Physica A: Statistical Mechanics and its Applications, 2007, 374( 1): 483–490

[22] Ali H T, Couillet R . Improved spectral community detection in large heterogeneous networks. The Journal of Machine Learning Research, 2017, 18( 1): 8344–8392

[23] Kumar S, Panda B S, Aggarwal D. Community detection in complex networks using network embedding and gravitational search algorithm. Journal of Intelligent Information Systems, 2021, 57(1): 51–72

[24] Karaaslanlı A, Aviyente S . Community detection in dynamic networks: equivalence between stochastic blockmodels and evolutionary spectral clustering. IEEE Transactions on Signal and Information Processing over Networks, 2021, 7: 130–143

[25] Gupta P, Bahga S S. High-resolution numerical simulations of electrophoresis using the Fourier pseudo-spectral method. Electrophoresis, 2021, 42(7 − 8): 890 − 898

[26] Li Y, Sha C, Huang X, Zhang Y. Community detection in attributed graphs: An embedding approach. In: Proceedings of the 32nd AAAI conference on artificial intelligence. 2018

[27] Chung F R K. Spectral Graph Theory. Providence: American Mathematical Society, 1997

[28] Leonardi N, Van De Ville D . Tight wavelet frames on multislice graphs. IEEE Transactions on Signal Processing, 2013, 61( 13): 3357–3367

[29] Zellmer C, Tran T A, Sridhar S. Seeing the bigger picture. Nature Reviews Microbiology, 2021, 19(12): 745 −745

[30] Mason J C, Handscomb D C. Chebyshev polynomials. Chapman and Hall/CRC, 2002

[31] Phillips G M. Interpolation and approximation by polynomials. Springer Science \& Business Media, 2003

[32] Rivlin T J. Chebyshev Polynomials. Mineola: Dover Publications, Inc., 2020

[33] Newman M E J . Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103( 23): 8577–8582

[34] Yang J, Leskovec J . Defining and evaluating network communities based on ground−truth. Knowledge and Information Systems, 2015, 42( 1): 181–213

[35] Sales-Pardo M, Guimera R, Moreira A A, Nunes Amaral L A. Extracting the hierarchical organization of complex systems. Proceedings of the National Academy of Sciences, 2007, 104(39): 15224−15229

[36] Bian Y, Yan Y, Cheng W, Wang W, Luo D, Zhang X. On multi−query local community detection. In: Proceedings of IEEE International Conference on Data Mining. 2018, 9–18

[37] He K, Sun Y, Bindel D, Hopcroft J, Li Y. Detecting overlapping communities from local spectral subspaces. In: Proceedings of IEEE International Conference on Data Mining. 2015: 769 − 774

[38] He K, Shi P, Bindel D, Hopcroft J E . Krylov subspace approximation for local community detection in large networks. ACM Transactions on Knowledge Discovery from Data, 2019, 13( 5): 1–30

[39] Tremblay N, Borgnat P . Graph wavelets for multiscale community mining. IEEE Transactions on Signal Processing, 2014, 62( 20): 5227–5239

[40] Luo W, Zhang D, Ni L, Lu N . Multiscale local community detection in social networks. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 3): 1102–1112

RIGHTS & PERMISSIONS

Higher Education Press