Abstract
With the continuous development of business intelligence and scientific exploration, graphs have been extensively applied to various fields. Graph clustering has emerged as a crucial task for mining the structure and function of complex networks. However, existing clustering algorithms often overly emphasize the density and degree of vertices in the graph while neglecting the correlations and structural characteristics among vertices, resulting in poor performance when clustering graphs. In this paper, we propose a novel method called Structural and Cyclic Similarity (SCS) for structural graph clustering, aiming to improve the quality of clustering. Our method utilizes short-length cycles and paths, which are common graph motifs, to comprehensively capture the neighborhoods and graph motifs of connected vertices. This enables us to quantify the similarity between vertices effectively. The SCS is then applied to structural graph clustering algorithms, thereby improving the clustering quality. To efficiently compute the SCS, we give an algorithm of subgraph counting, which rapidly counts all short-length cycles in the graph. Experimental results conducted on six real-world datasets demonstrate that the clustering algorithm based on SCS outperforms other similarity measures in terms of clustering quality and can improve the effectiveness of graph clustering.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles (1998)
Augsten, N., BHlen, M.H.: Similarity joins in relational database systems. Synth. Lect. Data Manage. 5(5), 1–124 (2013)
Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient algorithms for large-scale local triangle counting. ACM Trans. Knowl. Disc. Data. 4, 1–8 (2010)
Chang, L., Wei, L., Lin, X., Lu, Q., Zhang, W.: pSCAN: fast and exact structural graph clustering. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE) (2016)
Chen, J., Hsu, W., Lee, M.L., Ng, S.K.: Nemofinder: dissecting genome-wide protein-protein interactions with Meso-scale network motifs. In: Twelfth ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2006)
Ding, C., He, X., Zha, H., Ming, G., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings 2001 IEEE International Conference on Data Mining (2001)
Feng, H.B.: Density-based shrinkage for revealing hierarchical and overlapping community structure in networks. Statist. Mech. App. Phys. A. 390, 2160–2171 (2011)
Feng, Z., Xu, X., Yuruk, N., Schweiger, T.A.J.: A novel similarity-based modularity function for graph partitioning (2007)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)
Grochow, J.A., Kellis, M.: Network motif discovery using subgraph enumeration and symmetry-breaking. In: Speed, T., Huang, H. (eds.) RECOMB 2007. LNCS, vol. 4453, pp. 92–106. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71681-5_7
Guimerà, R., Nunes Amaral, L.A.: Functional cartography of complex metabolic networks. Nature 433, 895–900 (2005)
Halkidi, M., Batistakis, Y., Vazirgiannis, M.: Cluster validity methods: part i. ACM SIGMOD Record 31(2), 40–45 (2002)
Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985)
Kim, M.S., Han, J.: A particle-and-density based evolutionary clustering method for dynamic networks. Proc. VLDB Endow. 2(1), 622–633 (2009)
Kutzkov, K., Pagh, R.: On the streaming complexity of computing local clustering coefficients. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining (2013)
Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoret. Comput. Sci. 407, 458–473 (2008)
Lim, S., Ryu, S., Kwon, S., Jung, K., Lee, J.G.: LinkSCAN*: overlapping community detection using the link-space transformation. In: IEEE International Conference on Data Engineering (2014)
Liu, J., Chi, W., Danilevsky, M., Han, J.: Large-scale spectral clustering on graphs. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (2013)
Lu, W., Xiao, Y., Shao, B., Wang, H.: How to partition a billion-node graph. In: IEEE International Conference on Data Engineering (2014)
Milo, R., Shen-Orr, S., Ltzkovitz, S., Kashtan, N., Alan, U.: Network motifs: Simple building blocks of complex networks (2011)
Newman, M., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2 Pt 2), 026113 (2004)
Pinar, A., Seshadhri, C., Vishal, V.: Escape: efficiently counting all 5-vertex subgraphs. In: The Web Conference (2017)
Shi, J., Malik, J.M.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905 (2000)
Shiokawa, H., Fujiwara, Y., Onizuka, M.: Fast algorithm for modularity-based graph clustering. In: National Conference on Artificial Intelligence (2013)
Shiokawa, H., Fujiwara, Y., Onizuka, M.: Scan++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs. VLDB Endow. 8, 1178–1189 (2015)
Singh, M.: SPICi: a fast clustering algorithm for large biological networks. Bioinformatics 26(8), 1105–11 (2010)
Sun, H., Huang, J., Han, J., Deng, H., Sun, Y.: Shrink: a structural clustering algorithm for detecting hierarchical communities in networks. In: ACM International Conference on Information & Knowledge Management (2010)
Sun, H., Huang, J., Han, J., Deng, H., Zhao, P., Feng, B.: gSkeletonClu: density-based network clustering via structure-connected tree division or agglomeration (2010)
Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., Tsiarli, M.: Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2013)
Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications (1994)
Xu, X., Yuruk, N., Feng, Z., Schweiger, T.A.: Scan: a structural clustering algorithm for networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 824–833 (2007)
Zhao, P.: gSparsify: Graph motif based sparsification for graph clustering. ACM (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Li, J., Wang, L., Zhang, Z., Qin, X. (2024). SCS: A Structural Similarity Measure for Graph Clustering Based on Cycles and Paths. In: Song, X., Feng, R., Chen, Y., Li, J., Min, G. (eds) Web and Big Data. APWeb-WAIM 2023. Lecture Notes in Computer Science, vol 14331. Springer, Singapore. https://doi.org/10.1007/978-981-97-2303-4_22
Download citation
DOI: https://doi.org/10.1007/978-981-97-2303-4_22
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2302-7
Online ISBN: 978-981-97-2303-4
eBook Packages: Computer ScienceComputer Science (R0)