-
The reconstruction of network structure from data represents a significant scientific challenge in the field of complex networks, which has attracted considerable attention from the research community. The most of existing network reconstruction methods transform the problem into a series of linear equation systems, to solve the equations. Subsequently, truncation methods are used to determine the local structure of each node by truncating the solution of each equation system. However, truncation methods frequently exhibit inadequate accuracy, and lack methods of evaluating the truncatability of solutions to each system of equations, that is to say, the reconstructability of nodes. In order to address these issues, in this work an undirected network reconstruction method is proposed based on a Gaussian mixture model. In this method, a Gaussian mixture model is first used to cluster the solution results obtainedby solving a series of linear equations, and then the probabilities of the clustering results are utilized to depict the likelihood of connections between nodes. Subsequently, an index of reconstructibility is defined based on information entropy, thus the probability of connections between each node and other nodes can be used to measure the reconstructibility of each node. The proposed method is ultimately applied to undirected networks. Nodes identified with high reconstructibility are used as a training set to guide the structural inference of nodes with lower reconstrucibility, thus enhancing the reconstruction of the undirected network. The symmetrical properties of the undirected network are then employed to infer the connection probabilities of the remaining nodes with other nodes. The experiments on both synthetic and real data are conducted and a variety of methods are used for constructing linear equations and diverse dynamical models. Compared with the results from a previous truncated reconstruction method, the reconstruction outcomes are evaluated. The experimental results show that the method proposed in this work outperforms existing truncation reconstruction methods in terms of reconstruction performance, thus confirming the universality and effectiveness of the proposed method.
-
Keywords:
- network reconstruction /
- Gaussian mixture model /
- reconstructability /
- undirected networks
[1] Li X, Sun L, Ling M J, Peng Y 2023 Neurocomputing 549 126441Google Scholar
[2] 张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 物理学报 60 050501Google Scholar
Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501Google Scholar
[3] Gardner T S, Di Bernardo D, Lorenz D, Collins J J 2003 Science 301 102Google Scholar
[4] Geier F, Timmer J, Fleck C 2007 BMC Syst. Biol. 1 1Google Scholar
[5] Gao C, Fan Y, Jiang S H, Deng Y, Liu J M, Li X H 2021 IEEE Trans. Intell. Transp. Syst. 23 6509Google Scholar
[6] Zhou Y M, Li S P, Kundu T, Bai X W, Qin W 2021 IEEE Trans. Network Sci. Eng. 8 2249Google Scholar
[7] 张海峰, 王文旭 2020 物理学报 69 088906Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906Google Scholar
[8] Wang J Y, Zhang Y J, Xu C, Li J Z, Sun J C, Xie J R, Feng L, Zhou T S, Hu Y Q 2024 Nat. Commun. 15 2849Google Scholar
[9] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 物理学报 67 198901Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901Google Scholar
[10] Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos: An Interdisciplinary Journal of Nonlinear Science 28 013122Google Scholar
[11] Zhao J, Cheong K H 2024 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 54 6Google Scholar
[12] Guo Q T, Jiang X, Lei Y J, Li M, Ma Y F, Zheng Z M 2015 Phys. Rev. E 91 012822Google Scholar
[13] Li D D, Qian W Q, Sun X X, Han D, Sun M 2023 Appl. Math. Comput. 458 128233
[14] Lv X J, Fan D M, Li Q, Wang J L, Zhou L 2023 Physica A 627 129131Google Scholar
[15] 徐翔, 朱承, 朱先强 2021 物理学报 70 088901Google Scholar
Xu X, Zhu C, Zhu X Q 2021 Acta Phys. Sin. 70 088901Google Scholar
[16] Wang H, Ma C, Chen H S, Lai Y C, Zhang H F 2022 Nat. Commun. 13 3043Google Scholar
[17] Ma C, Wang H, Zhang H F 2023 Europhys. Lett. 144 21002Google Scholar
[18] 杨浦, 郑志刚 2012 物理学报 61 120508Google Scholar
Yang P, Zheng Z G 2012 Acta Phys. Sin. 61 120508Google Scholar
[19] Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 124Google Scholar
[20] Shen Z S, Wang W X, Fan Y, Di Z R, Lai Y C 2014 Nat. Commun. 5 4323Google Scholar
[21] Liu Q M, Ma C, Xiang B B, Chen H S, Zhang H F 2019 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 51 4639Google Scholar
[22] Zhang A B, Fan Y, Di Z R, Zeng A 2023 Chaos, Solitons Fractals 173 113712Google Scholar
[23] Wang W X, Lai Y C, Grebogi C, Ye J P 2011 Phys. Rev. X 1 021021
[24] Li G J, Li N, Liu S H, Wu X Q 2019 Chaos: An Interdisciplinary Journal of Nonlinear Science 29 053117Google Scholar
[25] Mei G F, Wu X Q, Wang Y F, Hu M, Lu J A, Chen G R 2017 IEEE Trans. Cybern. 48 754Google Scholar
[26] Pandey P K, Adhikari B 2017 IEEE Trans. Knowl. Data Eng. 29 2072Google Scholar
[27] Pandey P K, Adhikari B, Mazumdar M, Ganguly N 2020 IEEE Trans. Knowl. Data Eng. 34 3377Google Scholar
[28] Ma C, Chen H S, Lai Y C, Zhang H F 2018 Phys. Rev. E 97 022301
[29] Zhang Z, Zhao Y, Liu J, Wang S, Tao R, Xin R, Zhang J 2019 Appl. Network Sci. 4 1Google Scholar
[30] Xu X, Zhu X Q, Zhu C 2023 Complex Intell. Syst. 9 3131Google Scholar
[31] Mignone P, Pio G, D’ Elia D, Ceci M 2020 Bioinformatics 36 1553Google Scholar
[32] Reynolds D A 2009 Encyclopedia of Biometrics 741 659
[33] Wang Y, Chakrabarti D, Wang C X, Faloutsos C 2003 In 22nd International Symposium on Reliable Distributed Systems Florence, Italy, October 6–8, 2003 pp25–34
[34] Perotti J I, Tessone C J, Clauset A, Caldarelli G 2018 arXiv: 1806.07005 (Physics and Society
[35] Erds P, Rényi A 1960 Publ. Math. Inst. Hungar. Acad. Sci. 5 17
[36] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[37] Barabási A L, Albert R 1999 Science 286 509Google Scholar
[38] Li J W, Shen Z S, Wang W X, Grebogi C, Lai Y C 2017 Phys. Rev. E 95 032303
-
图 1 网络重构结果 (a)和(b)分别为求解两组一系列线性方程组的求解结果, 红色点表示存在连接关系的求解结果, 蓝色点表示不存在连接关系的求解结果; (c)为(a)中红色方框内节点求解结果的直方图分布; (d)为(b)中红色方框内节点求解结果的直方图分布. (a)和(b)中的横坐标表示网络中节点编号, 纵坐标表示线性方程组的求解结果, (c)和(d)中的横坐标表示线性方程组的求解结果, 纵坐标表示分布的数量
Figure 1. Network reconstruction results: (a) and (b) represent two different solution results for solving a series of linear equation systems, respectively, with red dots indicating solutions with connectivity and blue dots indicating solutions without connectivity; (c) represents histogram distribution of the solution result for the node within the red box in panel (a); (d) represents histogram distribution of the solution result for the node within the red box in panel (b). The horizontal axes in panels (a) and (b) represent the node number in the network, the vertical axes represent the solution results of the linear equation system, the horizontal axes in panels (c) and (d) represent the solution results of the linear equation system, and the vertical axes represent the number of distributions.
图 2 $ {H(i)} $与节点重构效果的关系 横坐标表示节点编号, 左纵坐标表示节点的可重构性指标负值$ {-H(i)} $, 右纵坐标表示重构效果F1
Figure 2. The relationship between $ {H(i)} $ and node reconstruction effect: The horizontal axis represents the node number, the left vertical axis represents the negative value of node’s reconfigurability index $ {-H(i)} $, and the right vertical axis represents the reconstruction effect F1
图 3 UNRGMM与TTM在合成网络中的重构效果比较 (a)和(d)为ER网络上的重构效果; (b)和(e)为WS网络上的重构效果; (c)和(f)为BA网络上的重构效果. 误差棒表示10次独立实验的标准差
Figure 3. Comparison of reconstruction effects between UNRGMM and TTM in synthetic networks: (a) and (d) represent the reconstruction effect on the ER network; (b) and (e) represent the reconstruction effect on the WS network; (c) and (f) represent the reconstruction effect on the BA network. The error bar represents standard deviation over ten independent trials.
图 4 UNRGMM与TTM在噪声干扰下的重构效果 (a)和(d)为ER网络上的重构效果; (b)和(e)为WS网络上的重构效果; (c)和(f)为BA网络上的重构效果. 误差棒表示10次独立实验的标准差
Figure 4. The reconstruction effect of UNRGMM and TTM under noise interference: (a) and (d) represent the reconstruction effect on the ER network; (b) and (e) represent the reconstruction effect on the WS network; (c) and (f) represent the reconstruction effect on the BA network. The error bar represents standard deviation over ten independent trials.
图 5 UNRGMM与TTM在不同平均度的合成网络中的重构效果 (a)和(d)为ER网络上的重构效果; (b)和(e)为WS网络上的重构效果; (c)和(f)为BA网络上的重构效果. 误差棒表示10次独立实验的标准差
Figure 5. The reconstruction effect of UNRGMM and TTM in synthetic networks with different average degrees: (a) and (d) represent the reconstruction effect on the ER network; (b) and (e) represent the reconstruction effect on the WS network; (c) and (f) represent the reconstruction effect on the BA network. The error bar represents standard deviation over ten independent trials.
图 6 UNRGMM与TTM在不同动力学下的重构效果 (a)和(d)为Ising动力学的重构效果; (b)和(e)为Game动力学的重构效果; (c)和(f)为Majority动力学的重构效果. 误差棒表示10次独立实验的标准差
Figure 6. The reconstruction effect of UNRGMM and TTM under different dynamics: (a) and (d) represent the reconstruction effect for Ising dynamics; (b) and (e) represent the reconstruction effect for Game dynamics; (c) and (f) represent the reconstruction effect for Majority dynamics. The error bar represents standard deviation over ten independent trials.
表 1 真实网络结构特征N和E分别是节点和连边数量; ${\langle k\rangle}$表示平均度; C和r分别是聚类系数和分类系数; H是异质性程度, 定义为${H= {\langle k^2\rangle}/{{\langle k\rangle}^{2}}}$
Table 1. Real networks structure characteristics. N and E are the number of nodes and edges, respectively; ${\langle k\rangle}$ indicates the average degree; C and r are clustering coefficients and classification coefficients, respectively; H is the degree heterogeneity, defined as ${H= {\langle k^2\rangle}/{{\langle k\rangle}^{2}}}$.
真实网络 N E $ {\langle k\rangle} $ C r H Karate 34 78 4.588 0.59 –0.476 1.693 Dolphins 62 159 5.129 0.29 –0.071 1.326 Football 115 613 10.661 0.4 0.162 1.007 Polbooks 105 441 8.40 0.49 –0.128 1.421 表 2 UNRGMM与TTM在真实网络中的重构结果比较
Table 2. Comparison of reconstruction results between UNRGMM and TTM on real networks.
真实网络 TTM UNRGMM F1 Accuracy F1 Accuracy Karate 0.723 0.889 0.989 0.997 Dolphins 0.776 0.951 0.970 0.995 Football 0.484 0.874 0.774 0.963 Polbooks 0.571 0.896 0.838 0.978 -
[1] Li X, Sun L, Ling M J, Peng Y 2023 Neurocomputing 549 126441Google Scholar
[2] 张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 物理学报 60 050501Google Scholar
Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501Google Scholar
[3] Gardner T S, Di Bernardo D, Lorenz D, Collins J J 2003 Science 301 102Google Scholar
[4] Geier F, Timmer J, Fleck C 2007 BMC Syst. Biol. 1 1Google Scholar
[5] Gao C, Fan Y, Jiang S H, Deng Y, Liu J M, Li X H 2021 IEEE Trans. Intell. Transp. Syst. 23 6509Google Scholar
[6] Zhou Y M, Li S P, Kundu T, Bai X W, Qin W 2021 IEEE Trans. Network Sci. Eng. 8 2249Google Scholar
[7] 张海峰, 王文旭 2020 物理学报 69 088906Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906Google Scholar
[8] Wang J Y, Zhang Y J, Xu C, Li J Z, Sun J C, Xie J R, Feng L, Zhou T S, Hu Y Q 2024 Nat. Commun. 15 2849Google Scholar
[9] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 物理学报 67 198901Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901Google Scholar
[10] Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos: An Interdisciplinary Journal of Nonlinear Science 28 013122Google Scholar
[11] Zhao J, Cheong K H 2024 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 54 6Google Scholar
[12] Guo Q T, Jiang X, Lei Y J, Li M, Ma Y F, Zheng Z M 2015 Phys. Rev. E 91 012822Google Scholar
[13] Li D D, Qian W Q, Sun X X, Han D, Sun M 2023 Appl. Math. Comput. 458 128233
[14] Lv X J, Fan D M, Li Q, Wang J L, Zhou L 2023 Physica A 627 129131Google Scholar
[15] 徐翔, 朱承, 朱先强 2021 物理学报 70 088901Google Scholar
Xu X, Zhu C, Zhu X Q 2021 Acta Phys. Sin. 70 088901Google Scholar
[16] Wang H, Ma C, Chen H S, Lai Y C, Zhang H F 2022 Nat. Commun. 13 3043Google Scholar
[17] Ma C, Wang H, Zhang H F 2023 Europhys. Lett. 144 21002Google Scholar
[18] 杨浦, 郑志刚 2012 物理学报 61 120508Google Scholar
Yang P, Zheng Z G 2012 Acta Phys. Sin. 61 120508Google Scholar
[19] Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 124Google Scholar
[20] Shen Z S, Wang W X, Fan Y, Di Z R, Lai Y C 2014 Nat. Commun. 5 4323Google Scholar
[21] Liu Q M, Ma C, Xiang B B, Chen H S, Zhang H F 2019 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 51 4639Google Scholar
[22] Zhang A B, Fan Y, Di Z R, Zeng A 2023 Chaos, Solitons Fractals 173 113712Google Scholar
[23] Wang W X, Lai Y C, Grebogi C, Ye J P 2011 Phys. Rev. X 1 021021
[24] Li G J, Li N, Liu S H, Wu X Q 2019 Chaos: An Interdisciplinary Journal of Nonlinear Science 29 053117Google Scholar
[25] Mei G F, Wu X Q, Wang Y F, Hu M, Lu J A, Chen G R 2017 IEEE Trans. Cybern. 48 754Google Scholar
[26] Pandey P K, Adhikari B 2017 IEEE Trans. Knowl. Data Eng. 29 2072Google Scholar
[27] Pandey P K, Adhikari B, Mazumdar M, Ganguly N 2020 IEEE Trans. Knowl. Data Eng. 34 3377Google Scholar
[28] Ma C, Chen H S, Lai Y C, Zhang H F 2018 Phys. Rev. E 97 022301
[29] Zhang Z, Zhao Y, Liu J, Wang S, Tao R, Xin R, Zhang J 2019 Appl. Network Sci. 4 1Google Scholar
[30] Xu X, Zhu X Q, Zhu C 2023 Complex Intell. Syst. 9 3131Google Scholar
[31] Mignone P, Pio G, D’ Elia D, Ceci M 2020 Bioinformatics 36 1553Google Scholar
[32] Reynolds D A 2009 Encyclopedia of Biometrics 741 659
[33] Wang Y, Chakrabarti D, Wang C X, Faloutsos C 2003 In 22nd International Symposium on Reliable Distributed Systems Florence, Italy, October 6–8, 2003 pp25–34
[34] Perotti J I, Tessone C J, Clauset A, Caldarelli G 2018 arXiv: 1806.07005 (Physics and Society
[35] Erds P, Rényi A 1960 Publ. Math. Inst. Hungar. Acad. Sci. 5 17
[36] Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar
[37] Barabási A L, Albert R 1999 Science 286 509Google Scholar
[38] Li J W, Shen Z S, Wang W X, Grebogi C, Lai Y C 2017 Phys. Rev. E 95 032303
Catalog
Metrics
- Abstract views: 1131
- PDF Downloads: 39
- Cited By: 0