搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

确定度分布条件下可变同配系数的算法构造与影响分析

李静 张洪欣 王小娟 金磊

引用本文:
Citation:

确定度分布条件下可变同配系数的算法构造与影响分析

李静, 张洪欣, 王小娟, 金磊

Algorithm design and influence analysis of assortativity changing in given degree distribution

Li Jing, Zhang Hong-Xin, Wang Xiao-Juan, Jin Lei
PDF
导出引用
  • 复杂网络是现实中大量节点和边的抽象拓扑, 如何揭示网络内部拓扑对网络连通性、脆弱性等特征的影响是当前研究的热点. 本文在确定度分布的条件下, 根据Newman提出的同配系数的定义分析其影响因素. 首先在可变同配系数下分别提出了基于度分布的确定算法和基于概率分布的不确定算法, 并分别在三种不同类型的网络(Erds-Rnyi网络, Barabsi-Albert网络, Email真实网络)中验证. 实验结果表明: 当网络规模达到一定程度时, 确定算法优于贪婪算法. 以此为基础, 分析了同配系数改变时聚类系数的变化, 发现两者之间存在关联性, 并从网络的微观结构变化中揭示了聚类系数变化的原因.
    Complex network is the abstract topology of a large number of nodes and edges in reality. How to reveal the influences of internal network topology on network connectivity and vulnerability characteristics is a hotspot of current research. In this paper, we analyze the influence of assortativity according to Newman's definition of assortativity in a given degree distribution. To fully understand the influence of assortativity we should change the assortativity to see how the topology of network changes. But we find the existing greedy algorithm cannot improve assortativity effectively. First we put forward a deterministic algorithm based on degree distribution and an uncertain algorithm based on probability distribution to increase assortativity. The deterministic algorithm can create a certain network which has a large assortativity without changing node degree. The uncertain algorithm can increase the assortativity continuously by changing the connection of edges. And the uncertain algorithm creates different graphs each time, so the result of the algorithm is uncertain. Then we test our algorithms on three networks (ER network, BA network, Email network) and compare with greedy algorithm, and the experimental results show that the uncertain algorithm performs better than greedy algorithm in three networks which have a large span of assortativity. And our deterministic algorithm performs well in a real world network. We find that we can increase assortativity coefficient up to 1 in ER network. This is because nodes in the ER network are peer to peer. We can also show that that the assortativity cannot increase up to 1 in some networks because nodes in these networks are not in the same status. Because we obtain a large span of assortativity, we can fully understand the change of network topology. On this basis, we analyze the changes of clustering coefficient when using the uncertain algorithm based on a probability distribution to increase the assortativity. We find that there is a certain correlation between assortativity and clustering. And we study the micro influence of uncertain algorithm on network, by which the reason of the change of clustering coefficient is explained. We calculate the changes of giant branches and small branches. The changes of the number of nodes in giant branches and the number of small branches show that the scale of giant branches becomes smaller, which means that the connection between nodes in giant branches becomes closer. The increase of the number of small branches means that the network as a whole becomes more fragile. So we can show how the uncertain algorithm changes the topology of the network without changing the degree of nodes in the network. Then we can use this algorithm to change the network to obtain a larger span of assortativity for further study.
      通信作者: 王小娟, wj2718@163.com
    • 基金项目: 国家自然科学基金(批准号: 61571063, 61472357, 61501100, 61571059)资助的课题.
      Corresponding author: Wang Xiao-Juan, wj2718@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61571063, 61472357, 61501100, 61571059).
    [1]

    Newman M E J 2007 Phys. Rev. E 76 045101

    [2]

    Juyong P, Newman M E J 2003 Phys. Rev. E 68 026112

    [3]

    Wu Zh X, Guan J Y, Wang Y H, Feng C F 2010 Chin. Phys. B 19 060203

    [4]

    Quintana R, Kopcow L, Marconi G, Sueldo C, Speranza G, Baraao R I 2001 Human. Rep. 16 1814

    [5]

    Schwarte N, Cohen R, Ben-Avraham D, Barabsi A L, Havlin S 2002 Phys. Rev. E 66 015104

    [6]

    Dorogovtsev S N, Mendes J F F, Samukhin A N 2001 Phys. Rev. E 64 1107

    [7]

    Newman M E J, Strogatz S H, D J 2001 Phys. Rev. E 64 359

    [8]

    Litvak N 2013 Phys. Rev. E 87 522

    [9]

    Winterbach W, Ridder D D, Wang H J, Reinders M, Mieghem P V 2012 Europ. Phys. J. B 85 151

    [10]

    Zhang D Y, Bi-Feia H E, Chen P 2013 Complex Systems Complexity Science 10 45

    [11]

    Yang R 2014 Acm Southeast Regional Conference 1 5

    [12]

    Mussmann S, Moore J 2015 Proceedings of the 29th AAAI Conference on Artificial Intelligence 238 25

    [13]

    Newman M E J 2002 Phys. Rev. Lett. 89 111

    [14]

    Mieghem P V 2011 Performance Analysis of Communications Networks and Systems (Cambridge: Cambridge University Press) p20

    [15]

    Thedchanamoorthy G, Piraveenan M, Kasthuriratna D, Senanayake U 2014 Proc. Comput. Sci. 29 2449

    [16]

    Xin L, Tsuyoshi M, Ken W 2014 Phys. Rev. E 90 012806

    [17]

    Dwivedi S 2015 Phys. Rev. E 92 022802

  • [1]

    Newman M E J 2007 Phys. Rev. E 76 045101

    [2]

    Juyong P, Newman M E J 2003 Phys. Rev. E 68 026112

    [3]

    Wu Zh X, Guan J Y, Wang Y H, Feng C F 2010 Chin. Phys. B 19 060203

    [4]

    Quintana R, Kopcow L, Marconi G, Sueldo C, Speranza G, Baraao R I 2001 Human. Rep. 16 1814

    [5]

    Schwarte N, Cohen R, Ben-Avraham D, Barabsi A L, Havlin S 2002 Phys. Rev. E 66 015104

    [6]

    Dorogovtsev S N, Mendes J F F, Samukhin A N 2001 Phys. Rev. E 64 1107

    [7]

    Newman M E J, Strogatz S H, D J 2001 Phys. Rev. E 64 359

    [8]

    Litvak N 2013 Phys. Rev. E 87 522

    [9]

    Winterbach W, Ridder D D, Wang H J, Reinders M, Mieghem P V 2012 Europ. Phys. J. B 85 151

    [10]

    Zhang D Y, Bi-Feia H E, Chen P 2013 Complex Systems Complexity Science 10 45

    [11]

    Yang R 2014 Acm Southeast Regional Conference 1 5

    [12]

    Mussmann S, Moore J 2015 Proceedings of the 29th AAAI Conference on Artificial Intelligence 238 25

    [13]

    Newman M E J 2002 Phys. Rev. Lett. 89 111

    [14]

    Mieghem P V 2011 Performance Analysis of Communications Networks and Systems (Cambridge: Cambridge University Press) p20

    [15]

    Thedchanamoorthy G, Piraveenan M, Kasthuriratna D, Senanayake U 2014 Proc. Comput. Sci. 29 2449

    [16]

    Xin L, Tsuyoshi M, Ken W 2014 Phys. Rev. E 90 012806

    [17]

    Dwivedi S 2015 Phys. Rev. E 92 022802

  • [1] 刘俊群. 天线方向系数的一类计算逼近方法. 物理学报, 2020, 69(2): 028401. doi: 10.7498/aps.69.20191268
    [2] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [3] 牛弘, 张国山. 一类具有可变系数的混沌系统的同步. 物理学报, 2013, 62(13): 130502. doi: 10.7498/aps.62.130502
    [4] 余晓平, 裴韬. 手机通话网络度特征分析. 物理学报, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
    [5] 王丹, 郝彬彬. 一类高聚类系数的加权无标度网络及其同步能力分析. 物理学报, 2013, 62(22): 220506. doi: 10.7498/aps.62.220506
    [6] 王丹, 井元伟, 郝彬彬. 扩展HK网络结构与同步能力的研究. 物理学报, 2012, 61(22): 220511. doi: 10.7498/aps.61.220511
    [7] 田立新, 贺莹环, 黄益. 一种新型二分网络类局域世界演化模型. 物理学报, 2012, 61(22): 228903. doi: 10.7498/aps.61.228903
    [8] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究. 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
    [9] 套格图桑, 那仁满都拉. 第二种椭圆方程构造变系数非线性发展方程的无穷序列新精确解. 物理学报, 2011, 60(9): 090201. doi: 10.7498/aps.60.090201
    [10] 丁光涛. 一维变系数耗散系统Lagrange函数和Hamilton函数的新构造方法. 物理学报, 2011, 60(4): 044503. doi: 10.7498/aps.60.044503
    [11] 套格图桑, 斯仁道尔吉. 构造变系数非线性发展方程精确解的一种方法. 物理学报, 2009, 58(4): 2121-2126. doi: 10.7498/aps.58.2121
    [12] 赵清贵, 孔祥星, 侯振挺. 简易广义合作网络度分布的稳定性. 物理学报, 2009, 58(10): 6682-6685. doi: 10.7498/aps.58.6682
    [13] 套格图桑, 斯仁道尔吉. 辅助方程构造带强迫项变系数组合KdV方程的精确解. 物理学报, 2008, 57(3): 1295-1300. doi: 10.7498/aps.57.1295
    [14] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [15] 郭进利, 汪丽娜. 幂律指数在1与3之间的一类无标度网络. 物理学报, 2007, 56(10): 5635-5639. doi: 10.7498/aps.56.5635
    [16] 闫 栋, 祁国宁. 大规模软件系统的无标度特性与演化模型. 物理学报, 2006, 55(8): 3799-3804. doi: 10.7498/aps.55.3799
    [17] 郭进利. 供应链型网络中双幂律分布模型. 物理学报, 2006, 55(8): 3916-3921. doi: 10.7498/aps.55.3916
    [18] 张培培, 何 阅, 周 涛, 苏蓓蓓, 常 慧, 周月平, 汪秉宏, 何大韧. 一个描述合作网络顶点度分布的模型. 物理学报, 2006, 55(1): 60-67. doi: 10.7498/aps.55.60
    [19] 潘灶烽, 汪小帆. 一种可大范围调节聚类系数的加权无标度网络模型. 物理学报, 2006, 55(8): 4058-4064. doi: 10.7498/aps.55.4058
    [20] 李 旲, 山秀明, 任 勇. 具有幂率度分布的因特网平均最短路径长度估计. 物理学报, 2004, 53(11): 3695-3700. doi: 10.7498/aps.53.3695
计量
  • 文章访问数:  5804
  • PDF下载量:  194
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-12-13
  • 修回日期:  2016-01-19
  • 刊出日期:  2016-05-05

/

返回文章
返回