-
从数据中推断网络的结构作为复杂网络中一个重要科学问题已得到广泛关注. 现有的网络重构方法大多将网络重构问题转化为一系列线性方程组的求解问题, 然后通过某种截断方法对每个方程组的解进行截断, 从而确定每个节点的局部结构. 然而现有的截断方法大多存在着精度不足的问题, 且少有方法衡量每个方程组解的可截断性, 即节点的可重构性. 为了解决这些问题, 本文提出了一种基于高斯混合模型的无向网络重构方法. 该方法首先将节点间连接关系的推断问题转化为一个聚类问题, 然后利用高斯混合模型进行求解, 得到每个节点与其他节点的连接概率, 并根据概率定义一个基于信息熵的可重构指标, 从而在真实网络结构未知的情况下衡量每个节点的可重构性. 将该方法用于无向网络中, 可以利用无向网络的对称特征, 将可重构性高的节点作为训练集指导可重构性低的节点进行结构推断, 从而更好地重构出无向网络. 最后, 通过在合成数据和真实数据上与现有的截断方法进行比较, 证明了该方法可以更有效地重构出网络结构.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 126441
Google Scholar
[2] 张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 物理学报 60 050501
Google Scholar
Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501
Google Scholar
[3] Gardner T S, Di Bernardo D, Lorenz D, Collins J J 2003 Science 301 102
Google Scholar
[4] Geier F, Timmer J, Fleck C 2007 BMC Syst. Biol. 1 1
Google Scholar
[5] Gao C, Fan Y, Jiang S H, Deng Y, Liu J M, Li X H 2021 IEEE Trans. Intell. Transp. Syst. 23 6509
Google Scholar
[6] Zhou Y M, Li S P, Kundu T, Bai X W, Qin W 2021 IEEE Trans. Network Sci. Eng. 8 2249
Google Scholar
[7] 张海峰, 王文旭 2020 物理学报 69 088906
Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906
Google 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 2849
Google Scholar
[9] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 物理学报 67 198901
Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901
Google 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 013122
Google Scholar
[11] Zhao J, Cheong K H 2024 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 54 6
Google Scholar
[12] Guo Q T, Jiang X, Lei Y J, Li M, Ma Y F, Zheng Z M 2015 Phys. Rev. E 91 012822
Google 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 129131
Google Scholar
[15] 徐翔, 朱承, 朱先强 2021 物理学报 70 088901
Google Scholar
Xu X, Zhu C, Zhu X Q 2021 Acta Phys. Sin. 70 088901
Google Scholar
[16] Wang H, Ma C, Chen H S, Lai Y C, Zhang H F 2022 Nat. Commun. 13 3043
Google Scholar
[17] Ma C, Wang H, Zhang H F 2023 Europhys. Lett. 144 21002
Google Scholar
[18] 杨浦, 郑志刚 2012 物理学报 61 120508
Google Scholar
Yang P, Zheng Z G 2012 Acta Phys. Sin. 61 120508
Google Scholar
[19] Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 124
Google Scholar
[20] Shen Z S, Wang W X, Fan Y, Di Z R, Lai Y C 2014 Nat. Commun. 5 4323
Google 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 4639
Google Scholar
[22] Zhang A B, Fan Y, Di Z R, Zeng A 2023 Chaos, Solitons Fractals 173 113712
Google 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 053117
Google Scholar
[25] Mei G F, Wu X Q, Wang Y F, Hu M, Lu J A, Chen G R 2017 IEEE Trans. Cybern. 48 754
Google Scholar
[26] Pandey P K, Adhikari B 2017 IEEE Trans. Knowl. Data Eng. 29 2072
Google Scholar
[27] Pandey P K, Adhikari B, Mazumdar M, Ganguly N 2020 IEEE Trans. Knowl. Data Eng. 34 3377
Google 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 1
Google Scholar
[30] Xu X, Zhu X Q, Zhu C 2023 Complex Intell. Syst. 9 3131
Google Scholar
[31] Mignone P, Pio G, D’ Elia D, Ceci M 2020 Bioinformatics 36 1553
Google 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 440
Google Scholar
[37] Barabási A L, Albert R 1999 Science 286 509
Google 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)中的横坐标表示线性方程组的求解结果, 纵坐标表示分布的数量
Fig. 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
Fig. 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次独立实验的标准差
Fig. 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次独立实验的标准差
Fig. 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次独立实验的标准差
Fig. 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次独立实验的标准差
Fig. 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 
下载: 导出CSV
表 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
下载: 导出CSV
-
[1] Li X, Sun L, Ling M J, Peng Y 2023 Neurocomputing 549 126441
Google Scholar
[2] 张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 物理学报 60 050501
Google Scholar
Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501
Google Scholar
[3] Gardner T S, Di Bernardo D, Lorenz D, Collins J J 2003 Science 301 102
Google Scholar
[4] Geier F, Timmer J, Fleck C 2007 BMC Syst. Biol. 1 1
Google Scholar
[5] Gao C, Fan Y, Jiang S H, Deng Y, Liu J M, Li X H 2021 IEEE Trans. Intell. Transp. Syst. 23 6509
Google Scholar
[6] Zhou Y M, Li S P, Kundu T, Bai X W, Qin W 2021 IEEE Trans. Network Sci. Eng. 8 2249
Google Scholar
[7] 张海峰, 王文旭 2020 物理学报 69 088906
Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906
Google 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 2849
Google Scholar
[9] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 物理学报 67 198901
Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901
Google 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 013122
Google Scholar
[11] Zhao J, Cheong K H 2024 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 54 6
Google Scholar
[12] Guo Q T, Jiang X, Lei Y J, Li M, Ma Y F, Zheng Z M 2015 Phys. Rev. E 91 012822
Google 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 129131
Google Scholar
[15] 徐翔, 朱承, 朱先强 2021 物理学报 70 088901
Google Scholar
Xu X, Zhu C, Zhu X Q 2021 Acta Phys. Sin. 70 088901
Google Scholar
[16] Wang H, Ma C, Chen H S, Lai Y C, Zhang H F 2022 Nat. Commun. 13 3043
Google Scholar
[17] Ma C, Wang H, Zhang H F 2023 Europhys. Lett. 144 21002
Google Scholar
[18] 杨浦, 郑志刚 2012 物理学报 61 120508
Google Scholar
Yang P, Zheng Z G 2012 Acta Phys. Sin. 61 120508
Google Scholar
[19] Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 124
Google Scholar
[20] Shen Z S, Wang W X, Fan Y, Di Z R, Lai Y C 2014 Nat. Commun. 5 4323
Google 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 4639
Google Scholar
[22] Zhang A B, Fan Y, Di Z R, Zeng A 2023 Chaos, Solitons Fractals 173 113712
Google 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 053117
Google Scholar
[25] Mei G F, Wu X Q, Wang Y F, Hu M, Lu J A, Chen G R 2017 IEEE Trans. Cybern. 48 754
Google Scholar
[26] Pandey P K, Adhikari B 2017 IEEE Trans. Knowl. Data Eng. 29 2072
Google Scholar
[27] Pandey P K, Adhikari B, Mazumdar M, Ganguly N 2020 IEEE Trans. Knowl. Data Eng. 34 3377
Google 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 1
Google Scholar
[30] Xu X, Zhu X Q, Zhu C 2023 Complex Intell. Syst. 9 3131
Google Scholar
[31] Mignone P, Pio G, D’ Elia D, Ceci M 2020 Bioinformatics 36 1553
Google 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 440
Google Scholar
[37] Barabási A L, Albert R 1999 Science 286 509
Google Scholar
[38] Li J W, Shen Z S, Wang W X, Grebogi C, Lai Y C 2017 Phys. Rev. E 95 032303
下载:
计量
- 文章访问数: 458
- PDF下载量: 18
- 被引次数: 0
