1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China 2. Guangxi Key Lab of Multi-source Information Mining and Security, Guangxi Normal University, Guilin 541004, China
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.
S Fortunato . Community detection in graphs. Physics Reports, 2010, 486( 3−5): 75–174
2
A, Capriello L, Altinay A Monti . 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
S, Li X, Song H, Lu L, Zeng M, Shi F Liu . 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
Y, Fang X, Huang L, Qin Y, Zhang W, Zhang R, Cheng X Lin . A survey of community search over big graphs. The VLDB Journal, 2020, 29( 1): 353–392
5
S, Forouzandeh M, Rostami K Berahmand . 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
J, Li H, Ma Q, Li Z, Li L Chang . 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
Y, Chang H, Ma L, Chang Z Li . Community detection with attributed random walk via seed replacement. Frontiers of Computer Science, 2022, 16( 5): 165324
8
J, Reichardt S Bornholdt . Statistical mechanics of community detection. Physical Review E, 2006, 74( 1): 016110
9
D K, Hammond P, Vandergheynst R Gribonval . Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2011, 30( 2): 129–150
10
Q, Liu Y, Zhu M, Zhao X, Huang J, Xu Y Gao . VAC: vertex−centric attributed community search. In: Proceedings of the 36th IEEE International Conference on Data Engineering. 2020, 937–948
11
Z, Yang X, Li X, Zhang W, Luo K Li . K−truss community most favorites query based on top−t. World Wide Web, 2022, 25( 2): 949–969
12
C Tsourakakis . The k−clique densest subgraph problem. In: Proceedings of the 24th International Conference on World wide Web. 2015, 1122–1132
13
S, Meng H, Yang X, Liu Z, Chen J, Xuan Y Wu . Personalized influential community search in large networks: a K−ECC−based model. Discrete Dynamics in Nature and Society, 2021, 2021: 5363946
14
J, Wei H, Ma Y, Liu Z, Li N Li . Hierarchical high−order co−clustering algorithm by maximizing modularity. International Journal of Machine Learning and Cybernetics, 2021, 12( 10): 2887–2898
15
Q, Li H, Ma J, Li Z, Li Y Jiang . Incorporating user preference into multi−community and outliers search. In: Proceedings of International Joint Conference on Neural Networks. 2021, 1–8
16
Q, Li H, Ma J, Li Z, Li Y Jiang . Searching target communities with outliers in attributed graph. Knowledge−Based Systems, 2022, 235: 107622
17
J, Gao J, Chen Z, Li J Zhang . ICS−GNN: lightweight interactive community search via graph neural network. Proceedings of the VLDB Endowment, 2021, 14( 6): 1006–1018
18
Y, Jiang Y, Rong H, Cheng X, Huang K, Zhao J Huang . Query driven-graph neural networks for community search: from non-attributed, attributed, to interactive attributed. 2021, arXiv preprint arXiv: 2104, 0358: 3
19
Luxburg U Von . A tutorial on spectral clustering. Statistics and Computing, 2007, 17( 4): 395–416
20
M E J Newman . Spectral methods for community detection and graph partitioning. Physical Review E, 2013, 88( 4): 042822
21
S, Zhang R S, Wang X S Zhang . 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
H T, Ali R Couillet . 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
A, Karaaslanlı S Aviyente . 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
F R K Chung . Spectral Graph Theory. Providence: American Mathematical Society, 1997
28
N, Leonardi De Ville D Van . 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
M E J Newman . 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
J, Yang J Leskovec . 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
Y, Bian Y, Yan W, Cheng W, Wang D, Luo X Zhang . 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
K, He P, Shi D, Bindel J E Hopcroft . Krylov subspace approximation for local community detection in large networks. ACM Transactions on Knowledge Discovery from Data, 2019, 13( 5): 1–30
39
N, Tremblay P Borgnat . Graph wavelets for multiscale community mining. IEEE Transactions on Signal Processing, 2014, 62( 20): 5227–5239
40
W, Luo D, Zhang L, Ni N Lu . Multiscale local community detection in social networks. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 3): 1102–1112
