Motif adjacency matrix and spectral clustering of directed weighted networks

Yike Wang; Gaoxia Wang; Ximei Hou; Fan Yang; Yike Wang; Gaoxia Wang; Ximei Hou; Fan Yang

doi:10.3934/math.2023706

AIMS Mathematics

2023, Volume 8, Issue 6: 13797-13814. doi: 10.3934/math.2023706

Previous Article Next Article

Research article Special Issues

Motif adjacency matrix and spectral clustering of directed weighted networks

College of Science and Three Gorges Mathematics Research Center, China Three Gorges University, Yichang, Hubei, 443002, China

Received: 24 November 2022 Revised: 23 March 2023 Accepted: 26 March 2023 Published: 12 April 2023
MSC : 62H30, 91D30

In the spectral clustering methods, different from the network division based on edges, some research has begun to divide the network based on network motifs; the corresponding objective function of partition also becomes related to the motif information. But, the related research on the directed weighted network needs to be further deepened. The weight of the network has a great influence on the structural attributes of the network, so it is necessary to extend the motif-based clustering to the weighted network. In this paper, a motif-based spectral clustering method for directed weighted networks is proposed. At the same time, this paper supplements the method of obtaining matrix expressions of the motif adjacency matrix in directed unweighted networks and provides a method to deal with the weight of networks, which will be helpful for the application research of motifs. This clustering method takes into account the higher-order connectivity patterns in networks and broadens the applicable range of spectral clustering to directed weighted networks. In this method, the motif-based clustering of directed weighted networks can be transformed into the clustering of the undirected weighted network corresponding to the motif-based adjacency matrix. The results show that the clustering method can correctly identify the partition structure of the benchmark network, and experiments on some real networks show that this method performs better than the method that does not consider the weight of networks.
- directed weighted networks,
- motif adjacency matrix,
- spectral clustering,
- mapping,
- motif conductance
Citation: Yike Wang, Gaoxia Wang, Ximei Hou, Fan Yang. Motif adjacency matrix and spectral clustering of directed weighted networks[J]. AIMS Mathematics, 2023, 8(6): 13797-13814. doi: 10.3934/math.2023706

Related Papers:

Abstract

In the spectral clustering methods, different from the network division based on edges, some research has begun to divide the network based on network motifs; the corresponding objective function of partition also becomes related to the motif information. But, the related research on the directed weighted network needs to be further deepened. The weight of the network has a great influence on the structural attributes of the network, so it is necessary to extend the motif-based clustering to the weighted network. In this paper, a motif-based spectral clustering method for directed weighted networks is proposed. At the same time, this paper supplements the method of obtaining matrix expressions of the motif adjacency matrix in directed unweighted networks and provides a method to deal with the weight of networks, which will be helpful for the application research of motifs. This clustering method takes into account the higher-order connectivity patterns in networks and broadens the applicable range of spectral clustering to directed weighted networks. In this method, the motif-based clustering of directed weighted networks can be transformed into the clustering of the undirected weighted network corresponding to the motif-based adjacency matrix. The results show that the clustering method can correctly identify the partition structure of the benchmark network, and experiments on some real networks show that this method performs better than the method that does not consider the weight of networks.

References

[1]	S. E. Schaeffe, Graph clustering, Comput. Sci. Rev., 1 (2007), 27–64. https://doi.org/10.1016/j.cosrev.2007.05.001 doi: 10.1016/j.cosrev.2007.05.001
[2]	W. E. Donath, A. J. Hoffman, Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices, IBM Techn. Discl. Bull., 15 (1972), 938–944.
[3]	Z. Wu, R. Leahy, An optimal graph theoretic approach to data clustering: theory and its application to image segmentation, IEEE T. Pattern Anal., 15 (1993), 1101–1113. https://doi.org/10.1109/34.244673 doi: 10.1109/34.244673
[4]	L. Hagen, A. B. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE T. Comput. Aid. D., 11 (1992), 1074–1085. https://doi.org/10.1109/43.159993 doi: 10.1109/43.159993
[5]	Estrada, Ernesto, D. J. Higham, Network properties revealed through matrix functions, SIAM Rev., 4 (2010), 696–714. https://doi.org/10.1137/090761070 doi: 10.1137/090761070
[6]	A. Y. Ng, M. I. Jordan, Y. Weiss, On spectral clustering: Analysis and an algorithm, Adv. Neural Inf. Process. Syst., 2001,849–856.
[7]	M. Boedihardjo, S. Deng, T. Strohmer, A performance guarantee for spectral clustering, SIAM J. Math. Data Sci., 3 (2021), 369–387. https://doi.org/10.1137/20M1352193 doi: 10.1137/20M1352193
[8]	V. Satuluri, S. Parthasarathy, Symmetrizations for clustering directed graphs, Proceedings of the 14th International Conference on Extending Database Technology, 2011,343–354. https://doi.org/10.1145/1951365.1951407 doi: 10.1145/1951365.1951407
[9]	R. Milo, Network motifs: Simple building blocks of complex networks, Science, 298 (2002), 824–827. https://doi.org/10.1126/science.298.5594.824 doi: 10.1126/science.298.5594.824
[10]	C. Li, Y. Tang, Z. Tang, J. Cao, Y. Zhang, Motif-based embedding label propagation algorithm for community detection, Int. J. Intell. Syst., 37 (2021), 1880–1902. https://doi.org/10.1002/int.22759 doi: 10.1002/int.22759
[11]	J. Shi, J. Malik, Normalized cuts and image segmentation, Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1997,731–737. https://doi.org/10.1109/CVPR.1997.609407 doi: 10.1109/CVPR.1997.609407
[12]	A. R. Benson, D. F. Gleich, J. Leskovec, Higher-order organization of complex networks, Science, 353 (2016), 163–166. https://doi.org/10.1126/science.aad9029 doi: 10.1126/science.aad9029
[13]	Y. L. Zhang, B. Wu, Y. Liu, J. N. Lv, Local community detection based on network motifs, Tsinghua Sci. Technol., 24 (2019), 716–727. https://doi.org/10.26599/TST.2018.9010106 doi: 10.26599/TST.2018.9010106
[14]	Y. Ge, H. Lu, P. Peng, Mixed-order spectral clustering for complex networks, Pattern Recogn., 117 (2021), 107964. https://doi.org/10.1016/j.patcog.2021.107964 doi: 10.1016/j.patcog.2021.107964
[15]	F. Xia, S. Yu, C. F. Liu, J. X. Li, I. Lee, CHIEF: Clustering with higher-order motifs in big networks, IEEE T. Netw. Sci. Eng., 9 (2022), 990–1005. https://doi.org/10.1109/TNSE.2021.3108974 doi: 10.1109/TNSE.2021.3108974
[16]	Y. F. Wang, H. Y. Wang, S. H. Zhang, A weighted higher-order network analysis of fine particulate matter (PM_2.5) transport in Yangtze River Delta, Phys. A (Amsterdam, Neth.), 496 (2018), 654–662. https://doi.org/10.1016/j.physa.2017.12.096 doi: 10.1016/j.physa.2017.12.096
[17]	X. Shen, X. Gong, X. Jiang, J. Yang, X. Hu, High-order organization of weighted microbial interaction network, 2018 IEEE International Conference on Bioinformatics and Biomedicine, 2018,206–209. https://doi.org/10.1109/BIBM.2018.8621218 doi: 10.1109/BIBM.2018.8621218
[18]	W. G. Underwood, A. Elliott, M. Cucuringu, Motif-based spectral clustering of weighted directed networks, Appl. Netw. Sci., 5 (2020), 62. https://doi.org/10.1007/s41109-020-00293-z doi: 10.1007/s41109-020-00293-z
[19]	M. E. J. Newman, Analysis of weighted networks, Phys. Rev. E, 70 (2004), 05613. https://doi.org/10.1103/PhysRevE.70.056131 doi: 10.1103/PhysRevE.70.056131
[20]	A. H. Roger, R. J. Charles, Matrix analysis, 2 Eds., Cambridge: Cambridge University Press, 2012.
[21]	P. J. Rousseeuw, Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, J. Comput. Appl. Math., 20 (1987), 53–65. https://doi.org/10.1016/0377-0427(87)90125-7 doi: 10.1016/0377-0427(87)90125-7
[22]	D. L. Davies, D. W. Bouldin, A cluster separation measure, IEEE T. Pattern Anal., PAMI-1 (1979), 224–227. https://doi.org/10.1109/TPAMI.1979.4766909 doi: 10.1109/TPAMI.1979.4766909
[23]	W. Zachary, An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33 (1977), 452–473.
[24]	J. Kunegis, KONECT: The Koblenz network collection, Proceedings of the 22nd International Conference on World Wide Web, 2013, 1343–1350. https://doi.org/10.1145/2487788.2488173 doi: 10.1145/2487788.2488173
[25]	A. Azad, A. Buluç, J. R. Gilbert, Parallel triangle counting and enumeration using matrix algebra, 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015,804–811. https://doi.org/10.1109/IPDPSW.2015.75 doi: 10.1109/IPDPSW.2015.75
[26]	D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9 (1990), 251–280.
[27]	S. Sieranoja, P. Frnti, Adapting k-means for graph clustering, Knowl. Inf. Syst., 64 (2022), 115–142. https://doi.org/10.1007/s10115-021-01623-y doi: 10.1007/s10115-021-01623-y

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)