搜索

x

留言板

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

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

具有双峰特性的双层超网络模型

卢文 赵海兴 孟磊 胡枫

具有双峰特性的双层超网络模型

卢文, 赵海兴, 孟磊, 胡枫
PDF
HTML
导出引用
导出核心图
  • 随着社会经济的快速发展, 社会成员及群体之间的关系呈现出了更复杂、更多元化的特点. 超网络作为一种描述复杂多元关系的网络, 已在不同领域中得到了广泛的应用. 服从泊松度分布的随机网络是研究复杂网络的开创性模型之一, 而在现有的超网络研究中, 基于ER随机图的超网络模型尚属空白. 本文首先在基于超图的超网络结构中引入ER随机图理论, 提出了一种ER随机超网络模型, 对超网络中的节点超度分布进行了理论分析, 并通过计算机仿真了在不同超边连接概率条件下的节点超度分布情况, 结果表明节点超度分布服从泊松分布, 符合随机网络特征并且与理论推导相一致. 进一步, 为更准确有效地描述现实生活中的多层、异质关系, 本文构建了节点超度分布具有双峰特性, 层间采用随机方式连接, 层内分别为ER-ER, BA-BA和BA-ER三种不同类型的双层超网络模型, 理论分析得到了三种双层超网络节点超度分布的解析表达式, 三种双层超网络在仿真实验中的节点超度分布均具有双峰特性.
      通信作者: 赵海兴, h.x.zhao@163.com ; 胡枫, qhhuf@163.com
    • 基金项目: 国家自然科学基金(批准号: 11661069, 61663041)、青海省科技计划项目(批准号: 2018-ZJ-777)和教育部春晖项目(批准号: Z2016101)资助的课题
    [1]

    Wuchty S 2001 Mol. Biol. Evol. 18 1694

    [2]

    Wasserman S, Faust K 1994 Social Network Analysis (Cambridge: Cambridge University Press) pp1−66

    [3]

    汪小帆, 李翔, 陈关荣 2012 网络科学导论 (北京: 高等教育出版社) 第194 −226页

    Wang X F, Li X, Chen G R 2012 Network Science: An Introduction (Beijing: Higher Education Press) pp194−226 (in Chinese)

    [4]

    Wang P, Xu B W, Wu Y R, Zhou X Y 2015 Sci. Chin. Inf. 58 011101

    [5]

    Lü L Y, Zhou T 2011 Phys. A 390 1150

    [6]

    Liben-Nowell D, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019

    [7]

    Newman M E J 2001 Proc. Natl. Acad. Sci. 98 404

    [8]

    Zhou T, Wang B H, Jin Y D, He D R, Zhang P P, He Y, Su B B, Chen K, Zhang Z Z, Liu J G 2007 Int. J. Mod. Phys. C 18 297

    [9]

    Berge C 1973 Graphs and Hypergraphs (New York: American Elsevier Publishing Company, Inc.) pp389−425

    [10]

    Camarinha-Matos L M, Afsarmanesh H 2003 Comput. Ind. 51 139

    [11]

    Wu Z Y, Duan J Q, Fu X C 2014 Appl. Math. Modell. 38 2961

    [12]

    胡枫, 赵海兴, 何佳倍, 李发旭, 李淑玲, 张子柯 2013 物理学报 62 198901

    Hu F, Zhao H X, He J B, Li F X, Li S L, Zhang Z K 2013 Acta Phys. Sin. 62 198901

    [13]

    Estrada E, Rodríguez-Velázquez J A 2006 Phys. A 364 581

    [14]

    Ghoshal G, Zlatić V, Caldarelli G, Newman M E J 2009 Phys. Rev. E 79 066118

    [15]

    Zlatić V, Ghoshal G, Caldarelli G 2009 Phys. Rev. E 80 036118

    [16]

    Zhang Z K, Liu C 2010 J. Stat. Mech. 10 1742

    [17]

    Wang J W, Rong L L, Deng Q H 2010 Eur. Phys. J. B 77 493

    [18]

    胡枫, 赵海兴, 马秀娟 2013 中国科学: 物理学 力学 天文学 43 16

    Hu F, Zhao H X, Ma X J 2013 Sci. China, Ser. G 43 16

    [19]

    郭进利, 祝昕昀 2014 物理学报 63 090207

    Guo J L, Zhu X J 2014 Acta Phys. Sin. 63 090207

    [20]

    索琪, 郭进利 2017 系统工程理论与实践 37 720

    Suo Q, Guo J L 2017 System Eng. Theor. Prac. 37 720

    [21]

    Zhou Z, Jin Z, Jin J 2019 J. Phys. A 123 765

    [22]

    李甍娜, 郭进利, 卞闻, 常宁戈, 肖潇, 陆睿敏 2017 复杂系统与复杂性科学 4 66

    Li M N, Guo J L, Bian W, Chang N G, Xiao X, Lu R M 2017 Complex Systems and Complexity Science 4 66

    [23]

    胡枫, 刘猛, 赵静 2018 复杂系统与复杂性科学 4 31

    Hu F, Liu M, Zhao J 2018 Complex Systems and Complexity Science 4 31

    [24]

    Fang J Q, Liu Q H, Tang M 2016 JAAC 6 12

    [25]

    刘强, 方锦清, 李永 2015 复杂系统与复杂性科学 12 64

    Liu Q, Fang J Q, Li Y 2015 Complex Systems and Complexity Science 12 64

    [26]

    Boccaletti S, Bianconi G, Criado R 2014 Phys. Rep. 544 1

    [27]

    蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛 2020 物理学报 69 088904

    Jiang W J, Liu R R, Fan T L, Liu S S, Lü L Y 2020 Acta Phys. Sin. 69 088904

    [28]

    杨喜艳, 吴亚豪, 张家军 2019 电子科技大学学报 10 12178

    Yang X Y, Wu Y H, Zhang J J 2019 J. Elec. Sci. Tech. Univ. 10 12178

    [29]

    Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

    [30]

    Xu X P, Liu F 2008 Phys. Lett. A 372 6727

    [31]

    Xue X F 2017 Phys. A 486 434

    [32]

    Lima F W S, Sousa A O, Sumuor M A 2008 Phys. A 387 3503

    [33]

    Zehmakan A N 2020 Discrete. Appl. Math. 277 280

    [34]

    李炎, 唐刚, 宋丽建, 寻之朋, 夏辉, 郝大鹏 2013 物理学报 62 046401

    Li Y, Tang G, Song L J, Xu Z P, Xia H, Hao D P 2013 Acta Phys. Sin. 62 046401

  • 图 1  “航空-铁路”双层超网络模型

    Fig. 1.  Airline-Railway double-layer hyper network.

    图 2  500个节点的随机3均匀超网络在不同连接概率p值时的节点超度分布 (a) $p = 0.004$; (b) $p = 0.006$; (c) $p = 0.008$; (d) $p = 0.01$

    Fig. 2.  The hyper degree distribution of 3-uniform random hyper networks under different p: (a) $p = 0.004$; (b) $p = 0.006$; (c) $p = 0.008$; (d) $p = 0.01$.

    图 3  双层3均匀EE超网络在不同层间超边连接概率时的节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

    Fig. 3.  The EE hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    图 4  双层3均匀BB超网络节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

    Fig. 4.  The BB hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    图 5  双层3均匀BE超网络模型节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

    Fig. 5.  The BE hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    表 1  EE双层3均匀超网络实验统计

    Table 1.  Experimental statistics of EE hyper network.

    ${N_1}$${N_2}$N${p_1} = {p_2}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
    50050010000.0060.00162375870994932
    0.01623750199232402616
    下载: 导出CSV

    表 2  BB双层3均匀超网络实验统计

    Table 2.  Experimental statistics of BB hyper network.

    ${N_1}$${N_2}$N${m_{10}} = {m_{20}}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
    500500100030.00162375126251188
    0.01623750199232402616
    下载: 导出CSV

    表 3  BE双层3均匀超网络实验统计

    Table 3.  Experimental statistics of BE hyper network.

    ${N_1}$${N_2}$N${m_{10}}$${p_2}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
    500500100030.0060.00162375126994560
    0.01623750124932402244
    下载: 导出CSV
  • [1]

    Wuchty S 2001 Mol. Biol. Evol. 18 1694

    [2]

    Wasserman S, Faust K 1994 Social Network Analysis (Cambridge: Cambridge University Press) pp1−66

    [3]

    汪小帆, 李翔, 陈关荣 2012 网络科学导论 (北京: 高等教育出版社) 第194 −226页

    Wang X F, Li X, Chen G R 2012 Network Science: An Introduction (Beijing: Higher Education Press) pp194−226 (in Chinese)

    [4]

    Wang P, Xu B W, Wu Y R, Zhou X Y 2015 Sci. Chin. Inf. 58 011101

    [5]

    Lü L Y, Zhou T 2011 Phys. A 390 1150

    [6]

    Liben-Nowell D, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019

    [7]

    Newman M E J 2001 Proc. Natl. Acad. Sci. 98 404

    [8]

    Zhou T, Wang B H, Jin Y D, He D R, Zhang P P, He Y, Su B B, Chen K, Zhang Z Z, Liu J G 2007 Int. J. Mod. Phys. C 18 297

    [9]

    Berge C 1973 Graphs and Hypergraphs (New York: American Elsevier Publishing Company, Inc.) pp389−425

    [10]

    Camarinha-Matos L M, Afsarmanesh H 2003 Comput. Ind. 51 139

    [11]

    Wu Z Y, Duan J Q, Fu X C 2014 Appl. Math. Modell. 38 2961

    [12]

    胡枫, 赵海兴, 何佳倍, 李发旭, 李淑玲, 张子柯 2013 物理学报 62 198901

    Hu F, Zhao H X, He J B, Li F X, Li S L, Zhang Z K 2013 Acta Phys. Sin. 62 198901

    [13]

    Estrada E, Rodríguez-Velázquez J A 2006 Phys. A 364 581

    [14]

    Ghoshal G, Zlatić V, Caldarelli G, Newman M E J 2009 Phys. Rev. E 79 066118

    [15]

    Zlatić V, Ghoshal G, Caldarelli G 2009 Phys. Rev. E 80 036118

    [16]

    Zhang Z K, Liu C 2010 J. Stat. Mech. 10 1742

    [17]

    Wang J W, Rong L L, Deng Q H 2010 Eur. Phys. J. B 77 493

    [18]

    胡枫, 赵海兴, 马秀娟 2013 中国科学: 物理学 力学 天文学 43 16

    Hu F, Zhao H X, Ma X J 2013 Sci. China, Ser. G 43 16

    [19]

    郭进利, 祝昕昀 2014 物理学报 63 090207

    Guo J L, Zhu X J 2014 Acta Phys. Sin. 63 090207

    [20]

    索琪, 郭进利 2017 系统工程理论与实践 37 720

    Suo Q, Guo J L 2017 System Eng. Theor. Prac. 37 720

    [21]

    Zhou Z, Jin Z, Jin J 2019 J. Phys. A 123 765

    [22]

    李甍娜, 郭进利, 卞闻, 常宁戈, 肖潇, 陆睿敏 2017 复杂系统与复杂性科学 4 66

    Li M N, Guo J L, Bian W, Chang N G, Xiao X, Lu R M 2017 Complex Systems and Complexity Science 4 66

    [23]

    胡枫, 刘猛, 赵静 2018 复杂系统与复杂性科学 4 31

    Hu F, Liu M, Zhao J 2018 Complex Systems and Complexity Science 4 31

    [24]

    Fang J Q, Liu Q H, Tang M 2016 JAAC 6 12

    [25]

    刘强, 方锦清, 李永 2015 复杂系统与复杂性科学 12 64

    Liu Q, Fang J Q, Li Y 2015 Complex Systems and Complexity Science 12 64

    [26]

    Boccaletti S, Bianconi G, Criado R 2014 Phys. Rep. 544 1

    [27]

    蒋文君, 刘润然, 范天龙, 刘霜霜, 吕琳媛 2020 物理学报 69 088904

    Jiang W J, Liu R R, Fan T L, Liu S S, Lü L Y 2020 Acta Phys. Sin. 69 088904

    [28]

    杨喜艳, 吴亚豪, 张家军 2019 电子科技大学学报 10 12178

    Yang X Y, Wu Y H, Zhang J J 2019 J. Elec. Sci. Tech. Univ. 10 12178

    [29]

    Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

    [30]

    Xu X P, Liu F 2008 Phys. Lett. A 372 6727

    [31]

    Xue X F 2017 Phys. A 486 434

    [32]

    Lima F W S, Sousa A O, Sumuor M A 2008 Phys. A 387 3503

    [33]

    Zehmakan A N 2020 Discrete. Appl. Math. 277 280

    [34]

    李炎, 唐刚, 宋丽建, 寻之朋, 夏辉, 郝大鹏 2013 物理学报 62 046401

    Li Y, Tang G, Song L J, Xu Z P, Xia H, Hao D P 2013 Acta Phys. Sin. 62 046401

  • 引用本文:
    Citation:
计量
  • 文章访问数:  423
  • PDF下载量:  11
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-07-04
  • 修回日期:  2020-08-31
  • 上网日期:  2020-12-22
  • 刊出日期:  2021-01-05

具有双峰特性的双层超网络模型

  • 1. 陕西师范大学计算机科学学院, 西安 710119
  • 2. 青海师范大学计算机学院, 西宁 810008
  • 3. 青海省藏文信息处理与机器翻译重点实验室, 西宁 810008
  • 4. 藏文信息处理教育部重点实验室, 西宁 810008
  • 通信作者: 赵海兴, h.x.zhao@163.com ; 胡枫, qhhuf@163.com
    基金项目: 国家自然科学基金(批准号: 11661069, 61663041)、青海省科技计划项目(批准号: 2018-ZJ-777)和教育部春晖项目(批准号: Z2016101)资助的课题

摘要: 随着社会经济的快速发展, 社会成员及群体之间的关系呈现出了更复杂、更多元化的特点. 超网络作为一种描述复杂多元关系的网络, 已在不同领域中得到了广泛的应用. 服从泊松度分布的随机网络是研究复杂网络的开创性模型之一, 而在现有的超网络研究中, 基于ER随机图的超网络模型尚属空白. 本文首先在基于超图的超网络结构中引入ER随机图理论, 提出了一种ER随机超网络模型, 对超网络中的节点超度分布进行了理论分析, 并通过计算机仿真了在不同超边连接概率条件下的节点超度分布情况, 结果表明节点超度分布服从泊松分布, 符合随机网络特征并且与理论推导相一致. 进一步, 为更准确有效地描述现实生活中的多层、异质关系, 本文构建了节点超度分布具有双峰特性, 层间采用随机方式连接, 层内分别为ER-ER, BA-BA和BA-ER三种不同类型的双层超网络模型, 理论分析得到了三种双层超网络节点超度分布的解析表达式, 三种双层超网络在仿真实验中的节点超度分布均具有双峰特性.

English Abstract

    • 复杂网络作为描述和分析现实生活中真实网络的网络系统, 在不同领域中得到了广泛的应用并取得了丰硕的成果[1-8]. 随着社会经济的快速发展, 现实生活中的网络呈现出了关系更复杂、节点属性更多元化的特点, 而一般的复杂网络难以全面、准确地刻画现实网络的特征. 鉴于超网络具有大数据、复杂性、多维性和多层次等特点, 使得描述和分析关系更复杂、节点属性更多元化的网络具有一定的实际应用价值[9-12]. 例如, 在航空超网络和铁路超网络之间根据乘客换乘行为依次连接机场和铁路站点, 形成“航空-铁路”双层超网络模型并在此网络模型的结构基础之上, 利用超图理论优化交通规划和乘客换乘行为. 如图1所示, 第一层超网络为航空超网络, 其中超边${A_1}$表示航班, 包含的节点${a_1}$, ${a_2}$${a_3}$表示该航班经过的三个机场; 第二层超网络为铁路超网络, 其中超边${R_1}$为铁路运营线路, 包含的节点${b_1}$, ${b_2}$, ${b_3}$, ${b_4}$, ${b_5}$, ${b_6}$${b_7}$表示该趟列车途经的站点. 两层超网络之间的超边${C_1}$表示乘客乘坐动车在${b_4}$站下车后可以选择${a_2}$${a_3}$机场换乘飞机, 超边${C_2}$表示若乘客乘坐动车在${b_{20}}$${b_{21}}$站下车, 如果打算继续换乘飞机那么就只能选择${a_6}$机场.

      图  1  “航空-铁路”双层超网络模型

      Figure 1.  Airline-Railway double-layer hyper network.

      近年来, 基于超图的超网络研究主要分为超网络的实际应用和模型构建两个方面. Estrada等[13]对超网络的子图中心度和聚集系数进行了系统研究, 并采用超网络描述了马来西亚热带雨林中的食物网络, 通过分析得到了食物竞争关系. Ghoshal等[14]提出并利用随机三部超图对社会化标签网络中的资源、用户和标签三类节点的度分布进行了理论分析, 得到了一些重要的结果. Zlatić等[15]在三部随机超图的基础之上, 扩展了超度分布、节点相似性和节点间最短路径等拓扑指标的定义, 为进一步研究社会化标签网络提供了一个标准工具. Zhang和Liu[16]提出了一种社会化标签网络的三部超图演化模型, 研究了该模型的超度、聚集系数和平均路径长度等拓扑特性, 并与实证数据做了对比. Wang等[17]和胡枫等[18]构建了基于超图理论的无标度超网络演化模型, 理论分析了该超网络模型的节点超度分布服从幂律分布, 并通过仿真实验验证了理论分析结果. 郭进利等[19,20]将文献[17]和文献[18]提出的超网络模型进行了统一, 分析了该统一超网络的无标度特性演化机理和拓扑特性. Zhou等[21]构建了一种同时考虑新超边增加和已存在超边消失的超网络模型. 李甍娜等[22]以唐诗为节点, 以韵母为超边构建了唐诗超网络, 发现该超网络服从无标度分布且具有较高的聚集性和异配性. 胡枫等[23]构建了蛋白复合物超网络模型, 并分析得出了识别关键蛋白的方法. 与此同时, 多层超网络的发展也极为迅速. 方锦清等[24,25]从多角度出发思考和探索了多层超网络, 提出了三层超网络演化模型, 定义了两种层次交叉度, 并用其描述了层间节点的合作竞争关系和超网络的鲁棒性. Boccaletti等[26]详细描述了多层网络, 并从基本结构入手分析了多层网络的动态变化过程. 蒋文君等[27]就多层网络级联失效的预防和级联失效后的恢复做了整体性讨论. 杨喜艳等[28]基于马尔科夫链方法建立了双层谣言传播网络模型, 并提出了一种能够有效阻止多层社交网络谣言传播的动态控制策略.

      网络模型既可以刻画网络的结构特征, 也可分析网络的动力学. ER随机网络模型是由匈牙利数学家Erdös和Rényi在[29]20世纪50年代末提出的, 是复杂网络和现实生活中最为常用的一种随机网络模型. 近年来, ER随机网络在不同领域得到了广泛的研究与应用, Xu[30]在ER随机网络模型中研究了经典的量子游走问题, 结果表明, 量子在游走过程中的返回概率, 即在初始节点找到量子的概率正比于ER随机网络的边连接概率, 且当ER随机网络趋于全连通时, 其返回概率会出现激增的现象. Xue[31]在ER随机网络中利用大数定律改进了SIR传播模型. Lima等[32]在有向ER随机网络上研究了多数投票模型, 通过蒙特卡罗模拟得到了“有序-无序”相变的关键参数. Zehmakan[33]将社会网络抽象为ER随机网络, 发现了社会成员的观念在网络连通性达到某个阈值时会发生改变. 李炎等[34]研究了ER随机网络中的Achlioptas爆炸渗流模型的相变性质, 结果表明, ER随机网络中的爆炸渗流相变是一种奇异相变, 它既不是标准的不连续相变, 又与常规随机渗流表现出的连续相变处于不同的普适类. 在经济快速发展和“大数据”时代的社会背景下, 超网络已经成为了网络科学的重要研究方向之一, 为更好地应用超网络, 超网络模型的构建是不能忽略的. 目前, 超网络模型的研究成果主要集中在无标度超网络模型的构建中, 对基于ER随机图理论的ER随机超网络模型研究尚属空白. 本文针对此问题, 首先提出了一种ER随机超网络模型的构建方法, 并分析得出了节点超度分布的解析表达式, 仿真实验结果表明, 本文提出的ER随机超网络的节点超度分布服从泊松分布, 符合随机网络特征并与理论推导一致. 为描述更为复杂的多层、异质关系的网络, 进一步构建了节点超度分布具有双峰特性, 层间采用随机方式连接, 层内分别为ER-ER, BA-BA和BA-ER三种不同类型的双层超网络模型, 理论分析得到了三种双层超网络节点超度分布的解析表达式, 并通过仿真实验对其进行了验证.

    • 在超图结构中引入ER随机图理论, 提出了一种ER随机超网络模型, 记为$H(N, p)$, 构建过程如下:

      1)初始化: 给定节点数量N和超边连接概率p, $p \in \left[ {0, 1} \right]$;

      2)在N个节点中任意选择r个不相同的节点, $r \leqslant N$;

      3)生成一个随机数s, $s \in \left( {0, 1} \right)$;

      4)如果$s < p$, 将第2步中选择的r个节点组成一条超边;

      5)重复2)—4)步, 直至所有的r个不相同的节点都被选择一次.

      在以上的构建过程中, 由于每次选择r个节点形成一条超边, 因此本模型构建的超网络为r均匀超网络. 最终生成的超边数量$m \approx p\left(\!\!\! {{array}{*{20}{c}} N \\ r {array}}\!\!\! \right)$.

    • 在本文提出的ER随机超网络中, 一个节点与其他$r - 1$个节点组成一条超边的概率为${p^k}{(1 - p)^{{{F}} - k}}$, 其中${{F}} = \left(\!\!\! {{array}{*{20}{c}} {N - 1} \\ {r - 1} {array}}\!\!\! \right)$, 则网络中一个给定节点超度为k的概率分布为:

      $p(k) = \left(\!\!\! {\begin{array}{*{20}{c}} {{F}} \\ k \end{array}} \!\!\!\right){p^k}{(1 - p)^{{{F}} - k}}.$

      网络节点的平均超度为

      $\left\langle k \right\rangle = p \times {{F}}.$

      所以, 当ER随机超网络的节点数N较大并且超边连接概率p较小时, 节点超度为k的二项分布近似为泊松分布:

      $p(k) = \left(\!\!\! {\begin{array}{*{20}{c}} {{F}} \\ k \end{array}}\!\!\! \right){p^k}{(1 - p)^{{{F}} - k}} \approx \frac{{{{\left\langle \lambda \right\rangle }^k}}}{{k!}}{{\rm{e}}^{ - \left\langle \lambda \right\rangle }},$

      其中, $ \left\langle \lambda \right\rangle = p \times {{F}}.$

    • 图2$N = 500$, $r = 3$时, 在超边连接概率$p = 0.004$, $p = 0.006$, $p = 0.008$$p = 0.01$四种不同条件下取100次平均值的节点超度分布情况.

      图  2  500个节点的随机3均匀超网络在不同连接概率p值时的节点超度分布 (a) $p = 0.004$; (b) $p = 0.006$; (c) $p = 0.008$; (d) $p = 0.01$

      Figure 2.  The hyper degree distribution of 3-uniform random hyper networks under different p: (a) $p = 0.004$; (b) $p = 0.006$; (c) $p = 0.008$; (d) $p = 0.01$.

      图2(a)图2(d)可以看出, 本文提出的ER随机超网络模型的节点超度分布在四种不同超边连接概率条件下均服从泊松分布并与理论分析结果一致, 符合随机网络特征.

    • 超网络在描述复杂多元关系的系统时有着较强的优势, 而随着一些实际研究工作的展开, 我们发现单层超网络在描述多层异质关系时会略显不足. 例如在交通网络中, 如何准确地描述航空超网络和铁路超网络之间的关系等. 针对此类问题, 本文构建了节点超度分布具有双峰特性的双层超网络模型, 层间采用随机方式连接, 层内分别为ER-ER, BA-BA和BA-ER三种不同类型的双层超网络模型(简记为EE, BB和BE, 其中E代表本文提出的ER随机超网络; B代表BA 无标度超网络). 本文以双层3均匀超网络为例, 分析三种不同类型的双层超网络模型.

    • EE双层3均匀超网络包含两层ER随机3均匀超网络, 层与层之间采用随机连接方式.

    • EE双层3均匀超网络模型的构建过程如下:

      1) 采用本文提出的ER随机超网络模型$H(N, p)$构建第一层和第二层超网络${H_1}({N_1}, {p_1})$${H_2}({N_2}, {p_2})$;

      2) 层间连接: 采用随机方式连接层间, 即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率${p_{12}}$组合生成一条超边, 直至层间形成${N_1}\left(\!\!\! {{array}{*{20}{c}} {{N_2}} \\ 2 {array}}\!\!\! \right){p_{12}}$条超边为止.

    • 根据以上构建方法中的第2步可知, EE双层超网络的节点平均超度$\left\langle k \right\rangle $由第一层超网络的节点平均超度$\left\langle {{k_1}} \right\rangle $和第二层超网络的节点平均超度$\left\langle {{k_2}} \right\rangle $决定. 其中, EE双层超网络中第一层网络中的任意一个节点与层内其他任意两个节点形成超边的数量为$\left(\!\!\! {{array}{*{20}{c}} {{N_1} - 1} \\ 2 {array}}\!\!\! \right){p_1}$, 与第二层超网络中的任意两个节点形成超边的数量为$\left(\!\!\! {{array}{*{20}{c}} {{N_2}} \\ 2 {array}} \!\!\! \right){p_{12}}$; 同理, 第二层超网络中任意一个节点在层内形成的超边数量为$\left(\!\!\! {{array}{*{20}{c}} {{N_2} - 1} \\ 2 {array}}\!\!\! \right){p_2}$, 第二层超网络中任意两个节点与第一层超网络中任意一个节点形成超边的数量为${N_2}\left( {{N_2} - 1} \right){p_{12}}$, 故第一层和第二层超网络节点平均超度的计算表达式为:

      $ \langle {k}_{1}\rangle =\left(\!\!\! \begin{array}{c}{N}_{1}-1\\ 2\end{array}\!\!\! \right){p}_{1}+\left(\!\!\! \begin{array}{c}{N}_{2}\\ 2\end{array}\!\!\! \right){p}_{12}, $

      $ \langle {k}_{2}\rangle =\left(\!\!\! \begin{array}{c}{N}_{2}-1\\ 2\end{array}\!\!\! \right){p}_{2}+{N}_{2}\left({N}_{2}-1\right){p}_{12}, $

      式中, ${N_1}$${N_2}$分别为第一层和第二层超网络的节点数, ${p_1}$${p_2}$分别为第一层和第二层超网络的层内超边连接概率, ${p_{12}}$为层间超边连接概率. 由(4)式和(5)式可得$\left\langle k \right\rangle = \dfrac{\left( {\left\langle {{k_1}} \right\rangle \times {N_1} + \left\langle {{k_2}} \right\rangle \times {N_2}} \right)} {\left( {{N_1} + {N_2}} \right)}$.

      EE双层超网络的节点超度分布由第一层超网络的节点超度分布${p^{{\rm{1 st}}}}(k)$和第二层超网络的节点超度分布${p^{{\rm{2 nd}}}}(k)$组成. 第一层超网络中任意一个节点与其他两个节点组成一条超边的概率为${p_1}^i(1 - {{p_1})^{{{{F}}_1} - i}}$, 其中${{{F}}_1} = \left(\!\!\! {{array}{*{20}{c}} {{N_1} - 1} \\ 2 {array}}\!\!\! \right)$, 与第二层超网络中的任意两个节点组成一条超边的概率为$p_{12}^{k - i} \times {(1 - {p_{12}})^{{{{Q}}_1} - (k - i)}}$, 其中${{{Q}}_1} = \left(\!\!\! {{array}{*{20}{c}} {{N_2}} \\ 2 {array}}\!\!\! \right)$. 由此可以得出第一层超网络中节点超度为k的概率分布为

      ${p^{{\rm{1st}}}}(k) = \dfrac{\displaystyle\sum\nolimits_{i = 0}^k {{N_1} \times \left( {\begin{array}{*{20}{c}} {{{{F}}_1}} \\ i \end{array}} \right) \times p_{_1}^i \times {{(1 - {p_1})}^{{{{F}}_1} - i}} \times \left( {\begin{array}{*{20}{c}} {{{{Q}}_1}} \\ {k - i} \end{array}} \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{{{{Q}}_1} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)}.$

      同理, 第二层超网络中节点超度为k的概率分布为

      ${p^{{\rm{2nd}}}}(k) = \dfrac{\displaystyle\sum\nolimits_{i = 0}^k {{N_2} \times \left(\!\!\! {\begin{array}{*{20}{c}} {{{{F}}_2}} \\ i \end{array}} \!\!\! \right) \times p_2^i \times {{(1 - {p_2})}^{{{{F}}_2} - i}} \times \left(\!\!\! {\begin{array}{*{20}{c}} {{{{Q}}_2}} \\ {k - i} \end{array}} \!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{{{{Q}}_2} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)},$

      其中, ${{{F}}_2} = \left(\!\!\! {{array}{*{20}{c}} {{N_2} - 1} \\ 2 {array}}\!\!\! \right)$, ${{{Q}}_2} = {N_2}\left( {{N_2} - 1} \right)$, ${{{Q}}_2} = 2{{{Q}}_1}$, 则:

      ${p^{{\rm{2nd}}}}(k) =\dfrac {\displaystyle\sum\nolimits_{i = 0}^k {{N_2} \times \left(\!\!\! {\begin{array}{*{20}{c}} {{{{F}}_2}} \\ i \end{array}} \!\!\! \right) \times p_2^i \times {{(1 - {p_2})}^{{{{F}}_2} - i}} \times \left( \!\!\! {\begin{array}{*{20}{c}} {2{{{Q}}_1}} \\ {k - i} \end{array}}\!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{2{{{Q}}_1} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)}.$

    • 在EE双层超网络节点超度分布仿真实验中, ${N_1}$${N_2}$取值为500, 层内连接概率${p_1}$${p_2}$为0.006, 层间连接概率${p_{12}}$分别为0.001和0.01, 为了结果的合理有效, 实验结果取了100次的平均值.

      表1为EE双层超网络节点超度分布实验的统计信息, 其中N代表双层网络的总节点数, M为层间的超边数量. 实验结果表明, EE双层超网络的节点超度分布在不同层间超边连接概率条件下均具有双峰特性, 如图3(a)图3(b)所示.

      ${N_1}$${N_2}$N${p_1} = {p_2}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
      50050010000.0060.00162375870994932
      0.01623750199232402616

      表 1  EE双层3均匀超网络实验统计

      Table 1.  Experimental statistics of EE hyper network.

      图  3  双层3均匀EE超网络在不同层间超边连接概率时的节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

      Figure 3.  The EE hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    • BB双层3均匀超网络包含两层3均匀无标度超网络, 层与层之间采用随机连接方式. 在构建3均匀无标度超网络时, 采用文献[17]提出的均匀无标度超网络模型构建方法, 记为$H({m_0}, m)$. 该超网络模型的节点超度分布服从幂律分布, 符合无标度网络特征. $H({m_0}, m)$模型的构建过程如下:

      1) 初始化: 给定初始${m_0}$个节点$\{ {v_1}, {v_2}, {v_3}, \cdots , {v_{m0}} \}$与一条包含这些节点的超边${E_0} = \{ {v_1}, {v_2}, {v_{3, }} \cdots , {v_{m0}} \}$;

      2) 超边增长: 每个时间步t添加m个节点$\left\{{v}_{t1}, {v}_{t2}, {v}_{t3}, \cdots , {v}_{tm}\right\}$与一个已存在的节点${v_i}$组合成一条新的超边${E}_{t}=\left\{{v}_{t1}, {v}_{t2}, {v}_{t3}, \cdots , {v}_{tm}, {v}_{i}\right\}$. 这个已存在节点的选取方式为“超度优先连接”, 即节点vi被选中的概率正比于这个节点的超度, 定义为:

      $\prod {{d_H}({v_i}) = \frac{{{d_H}({v_i})}}{{\displaystyle\sum\nolimits_j {{d_H}(j)} }}} ,$

      式中, 分子${d_H}\left( {{v_i}} \right)$为节点${v_i}$的超度, 分母表示当前网络中所有节点超度之和. 在该均匀无标度超网络中, 一个给定节点超度为k的概率分布为[18]

      $p(k) = m(m + 1){k^{ - (2 + m)}},$

      式中, m为每次添加新节点的个数, 当$m = 2$时, 该超网络为3均匀无标度超网络.

    • BB双层3均匀超网络模型的构建过程如下:

      1) 采用$H\left( {{m_0}, \;m} \right)$模型构建第一层和第二层3均匀无标度超网络${H_1}\left( {{m_{10}}, \;{m_1}} \right)$${H_2}\left( {{m_{20}}, \;{m_2}} \right)$;

      2) 层间连接: 采用随机方式连接层间, 即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率${p_{12}}$组合生成一条超边, 直至形成$({m_{10}} + {m_1})\left(\!\!\! {{array}{*{20}{c}} {({m_{20}} + {m_2})} \\ 2 {array}} \!\!\! \right){p_{12}}$条超边为止.

    • 由于第一层与第二层超网络均为3均匀无标度超网络, 每次增加2个新节点与1个已存在节点组合生成一条超边, 所以在层间连接之前, 各层超网络的节点平均超度约为${3 / 2}$. 由此可得, 第一层超网络的节点平均超度$\left\langle {{k_1}} \right\rangle $和第二层超网络的节点平均超度$\left\langle {{k_2}} \right\rangle $分别为:

      $\left\langle {{k_1}} \right\rangle \approx 1.5 + \left( \!\!\! {\begin{array}{*{20}{c}} {{N_2}} \\ 2 \end{array}} \!\!\! \right){p_{12}},$

      $\left\langle {{k_2}} \right\rangle \approx 1.5 + {N_2}\left( {{N_2} - 1} \right){p_{12}},$

      其中, ${N_2}$为第二层超网络的节点数, 则BB超网络的节点平均超度$\left\langle k \right\rangle = \dfrac{ {\left\langle {{k_1}} \right\rangle \times {N_1} + \left\langle {{k_2}} \right\rangle \times {N_2}} } {\left( {{N_1} + {N_2}} \right)}$.

      在具有N个节点的3均匀无标度超网络中, 超度为1的节点数$M(1)$的上下界为$ {N}/{2} + 1 \leqslant M(1) \leqslant N - 1$, 超度为2的节点数$M(2)$的上界为$M(2) \leqslant {N}/{2}$. 所以, BB双层超网络的第一层超网络中节点超度为k的概率分布为

      ${p^{{\rm{1st}}}}(k) =\dfrac { {{W_1}(1) + {W_1}(2) + \displaystyle\sum\nolimits_{i = 3}^k {{i^{ - 4}} \times } \left(\!\!\! {\begin{array}{*{20}{c}} {{{{Q}}_1}} \\ {k - i} \end{array}} \!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{{{Q}} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)},$

      其中, ${W}_{1}(1)={M}_{1}(1)\!\times\! \left(\!\!\! {array}{c}{{Q}}_{1}\\ k-1{array}\!\!\! \right){p}_{12}^{k-1}\!\times\! {(1-{p}_{12})}^{{{Q}}_{1}-(k-1)}, \;{W}_{1}(2)={M}_{1}(2)\!\times\! \left(\!\!\! {array}{c}{{Q}}\\ k-2{array}\!\!\! \right){p}_{12}^{k-2}\!\times\! {(1-{p}_{12})}^{{{Q}}_{1}-(k-2)}.$

      同理, 第二层超网络中节点超度为k的概率分布为

      ${p^{{\rm{2nd}}}}(k) = \dfrac{ {{W_2}(1) + {W_2}(2) + \displaystyle\sum\nolimits_{i = 3}^k {{i^{ - 4}} \times } \left(\!\!\! {\begin{array}{*{20}{c}} {2{{{Q}}_1}} \\ {k - i} \end{array}} \!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{2{{{Q}}_1} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)},$

      其中, ${W}_{2}(1)={M}_{2}(1)\!\times\! \left(\!\!\! {array}{c}2{{Q}}_{1}\\ k-1{array}\!\!\! \right){p}_{12}^{k-1}\!\times\! {(1\!-\!{p}_{12})}^{2{{Q}}_{1}-(k-1)},\; {W}_{2}(2)={M}_{2}(2)\!\times\! \left(\!\!\! {array}{c}2{{Q}}_{1}\\ k-2{array}\!\!\! \right){p}_{12}^{k-2}\!\times\! {(1\!-\!{p}_{12})}^{2{{Q}}_{1}-(k-2)}.$

    • 在BB双层超网络节点超度分布的仿真实验中, 第一层与第二层超网络的节点数${N_1} = {m_{10}} + {m_1}$${N_2} = {m_{20}} + {m_2}$取值为500, 其中各层初始节点${m_{10}}$${m_{20}}$均为3, 层间连接概率${p_{12}}$分别为0.001和0.01, 为了结果的合理有效, 实验结果取了100次的平均值.

      表2为BB超网络节点超度分布实验的统计信息. 与EE双层超网络的结果相同, BB双层超网络的节点超度分布在不同层间超边连接概率条件下均具有双峰特性, 如图4(a)图4(b)所示.

      ${N_1}$${N_2}$N${m_{10}} = {m_{20}}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
      500500100030.00162375126251188
      0.01623750199232402616

      表 2  BB双层3均匀超网络实验统计

      Table 2.  Experimental statistics of BB hyper network.

      图  4  双层3均匀BB超网络节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

      Figure 4.  The BB hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    • BE双层3均匀超网络由第一层3均匀无标度超网络和第二层ER随机3均匀超网络组成, 层与层之间采用随机连接方式.

    • BE双层3均匀超网络模型的构建过程如下:

      1)采用$H\left( {{m_0}, \;m} \right)$模型构建第一层超网络${H_1}\left( {{m_{10}}, \;{m_1}} \right)$;

      2)采用$H\left( {N, \;p} \right)$模型构建第二层超网络${H_2}\left( {{N_2}, \;{p_2}} \right)$;

      3) 层间连接: 采用随机方式连接层间, 即第一层中的任意一个节点与第二层中的任意两个不相同节点以概率${p_{12}}$组合生成一条超边, 直至形成$({m_{10}} + {m_1})\left(\!\!\! {{array}{*{20}{c}} {{N_2}} \\ 2 {array}} \!\!\! \right){p_{12}}$条超边为止.

    • BE双层超网络的节点平均超度$\left\langle k \right\rangle $由第一层无标度超网络的节点平均超度$\left\langle {{k_1}} \right\rangle $和第二层ER随机超网络的节点平均超度$\left\langle {{k_2}} \right\rangle $决定, 分别为:

      $\left\langle {{k_1}} \right\rangle \approx 1.5 + \left(\!\!\! {\begin{array}{*{20}{c}} {{N_2}} \\ 2 \end{array}} \!\!\! \right){p_{12}},$

      $\left\langle {{k_2}} \right\rangle = \left(\!\!\! {\begin{array}{*{20}{c}} {{N_2} - 1} \\ 2 \end{array}} \!\!\! \right){p_2} + {N_2}\left( {{N_2} - 1} \right){p_{12}},$

      其中, ${N_2}$为第二层超网络的节点数, ${p_2}$为第二层超网络的层内超边连接概率, ${p_{12}}$为层间超边连接概率, 则$\left\langle k \right\rangle = {{\left( {\left\langle {{k_1}} \right\rangle \times {N_1} + \left\langle {{k_2}} \right\rangle \times {N_2}} \right)} / {\left( {{N_1} + {N_2}} \right)}}$.

      BE双层超网络的节点超度分布与EE双层超网络和BB双层超网络类似, 由第一层无标度超网络的节点超度分布和第二层ER随机超网络的节点超度分布组成. 第一层超网络中节点超度为k的概率分布为

      ${p^{{\rm{1st}}}}(k) = \dfrac{ {{W_1}(1) + {W_1}(2) + \displaystyle\sum\nolimits_{i = 3}^k {{i^{ - 4}} \times } \left(\!\!\! {\begin{array}{*{20}{c}} {{{{Q}}_1}} \\ {k - i} \end{array}} \!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{{{Q}} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)},$

      其中, ${W}_{1}(1)={M}_{1}(1)\!\times\! \left(\!\!\! {array}{c}{{Q}}_{1}\\ k-1{array}\!\!\! \right){p}_{12}^{k-1}\times {(1\!-\!{p}_{12})}^{{{Q}}_{1}-(k-1)}, {W}_{1}(2)={M}_{1}(2)\!\times\! \left(\!\!\! {array}{c}{{Q}}_{1}\\ k-2{array}\!\!\! \right){p}_{12}^{k-2}\!\times\! {(1\!-\!{p}_{12})}^{{{Q}}_{1}-(k-2)}.$

      第二层超网络中节点超度为k的概率分布为

      ${p^{{\rm{2nd}}}}(k) = \dfrac{\displaystyle\sum\nolimits_{i = 0}^k {{N_2} \times \left(\!\!\! {\begin{array}{*{20}{c}} {{F_2}} \\ i \end{array}} \!\!\! \right) \times p_2^i \times {{(1 - {p_2})}^{{F_2} - i}} \times \left(\!\!\! {\begin{array}{*{20}{c}} {2{{{Q}}_1}} \\ {k - i} \end{array}}\!\!\! \right) \times p_{12}^{k - i} \times {{(1 - {p_{12}})}^{2{{{Q}}_1} - (k - i)}}} } {\left( {{N_1} + {N_2}} \right)},$

      其中, ${{{F}}_2} = \left(\!\!\! {{array}{*{20}{c}} {{N_2} - 1} \\ 2 {array}} \!\!\! \right), {{{Q}}_1} = \left(\!\!\! {{array}{*{20}{c}} {{N_2}} \\ 2 {array}} \!\!\! \right)$, ${p_2}$为第二层随机超网络的超边连接概率.

    • 在BE双层超网络的节点超度分布实验中, 第一层与第二层超网络的节点数${N_1} = {m_{10}} + {m_1}$${N_2}$取值为500, 其中第一层超网络的初始节点${m_{10}}$为3, 第二层超网络的超边连接概率${p_2}$为0.006, 层间连接概率${p_{12}}$分别为0.001和0.01, 为了结果的合理有效, 实验结果取了100次的平均值.

      表3为BE超网络节点超度分布实验的统计信息. BE双层超网络的节点超度分布与以上两种类型的双层超网络情况相同, 在不同的层间超边连接概率的条件下, 节点超度分布均具有双峰特性, 如图5(a)图5(b)所示.

      ${N_1}$${N_2}$N${m_{10}}$${p_2}$${p_{12}}$M$\left\langle {{k_1}} \right\rangle $$\left\langle {{k_2}} \right\rangle $$\left\langle k \right\rangle $
      500500100030.0060.00162375126994560
      0.01623750124932402244

      表 3  BE双层3均匀超网络实验统计

      Table 3.  Experimental statistics of BE hyper network.

      图  5  双层3均匀BE超网络模型节点超度分布 (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$

      Figure 5.  The BE hyper degree distribution of double-layer 3-uniform hyper network under different ${p_{12}}$: (a)${p_{12}} = 0.001$; (b)${p_{12}} = 0.01$.

    • 本文基于经典的ER随机模型构建了基于超图的ER随机超网络模型, 通过理论分析得到了该模型的节点超度分布$p(k) \approx \dfrac{{{{\left\langle \lambda \right\rangle }^k}}}{{k!}}{{\rm{e}}^{ - \left\langle \lambda \right\rangle }}$, 其中泊松分布的期望值$\lambda $与超边连接概率p有关, 计算机仿真实验结果与理论分析一致. 与普通的ER随机网络相比, 本文提出的ER随机超网络模型对于描述和分析关系更复杂、节点属性更多元化的随机社会网络具有一定的实际应用价值. 同时, 在ER随机超网络模型的基础之上, 构建了ER-ER, BA-BA和BA-ER三种不同类型的双层超网络模型. 理论分析发现, 三种双层超网络的节点平均超度与层间超边连接概率密切相关, 随着层间超边连接概率的增大网络节点的平均超度也随之增大; 仿真实验结果表明, 三种模型的节点超度分布在不同的层间超边连接概率条件下均具有双峰特性.

      本文提出的ER随机超网络模型和双层超网络模型对今后进一步研究此类超网络的熵、超网络动力学、超网络表示学习、超网络链路预测和交通超网络优化等提供了理论基础, 对研究多层超网络的演化具有一定的借鉴意义.

参考文献 (34)

目录

    /

    返回文章
    返回