超网络模型构建中优先连接方法研究

doi:10.19678/j.issn.1000-3428.0055984

计算机工程 ›› 2020, Vol. 46 ›› Issue (10): 103-111. doi: 10.19678/j.issn.1000-3428.0055984

超网络模型构建中优先连接方法研究

孟磊^1,2,3, 冶忠林^1,2,3, 赵海兴^1,2,3, 杨燕琳^1,2,3

1. 青海师范大学计算机学院, 西宁 810016;
2. 青海省藏文信息处理与机器翻译重点实验室, 西宁 810008;
3. 藏文信息处理教育部重点实验室, 西宁 810008

收稿日期:2019-09-11 修回日期:2019-10-16 发布日期:2019-10-31
作者简介:孟磊(1994-),男,硕士研究生,主研方向为复杂网络、超网络;冶忠林,副教授、博士;赵海兴(通信作者),教授、博士;杨燕琳,硕士研究生。
基金资助:
国家自然科学基金（11661069，61663041）；青海省科技厅项目（2019-ZJ-7012）。

Research on Preferential Connection Method in Construction of Hypernetwork Model

MENG Lei^1,2,3, YE Zhonglin^1,2,3, ZHAO Haixing^1,2,3, YANG Yanlin^1,2,3

1. College of Computer, Qinghai Normal University, Xining 810016, China;
2. Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province, Xining 810008, China;
3. Key Laboratory of Tibetan Information Processing, Ministry of Education, Xining 810008, China

Received:2019-09-11 Revised:2019-10-16 Published:2019-10-31

摘要/Abstract

摘要： 优先连接机制是复杂网络建模中常用的节点连接机制，超网络模型也可以通过优先连接演化而得到。目前对于超网络模型的增长演化研究较多，而对超网络优先连接方式的研究比较少见。针对超网络模型演化过程中优先连接问题进行研究，基于赌轮法和链表法实现优先连接，从而构建超网络演化模型，对构建的均匀超网络和随机超网络的特性进行分析，并通过调整超网络模型构建过程中旧节点的选择数量、新节点添加数量和网络规模，研究超度幂律分布斜率的变化规律。实验结果表明，利用赌轮法构建超网络模型的时间远大于链表法。

关键词: 复杂网络, 超网络模型, 优先连接, 赌轮法, 链表法, 超度幂律分布

Abstract: In complex network modeling,the hypernetwork model can derive from the preferential connection mechanism,which is the most commonly used node connection mechanism.At present,researches relevant to the hypernetwork model mainly focus on its growth and evolution,and pay less attention to its preferential connection modes.This paper studies the preferential connections in the evolution of the hypernetwork model,and realizes the preferential connections based on the roulette method and the linked list method to construct a hypernetwork evolution model.The characteristics of the constructed uniform hypernetwork and random hypernetwork are analyzed,and the variation laws of the power-law distribution slope of hyper-degrees are studied by adjusting the number of selected old nodes,adding new nodes,and increasing the network scale in construction of hypernetwork.Experimental results show that the roulette method takes much longer to construct a hypernetwork model than the linked list method does.

Key words: complex network, hypernetwork model, preferential connection, roulette method, linked list method, hyper-degree power law distribution

中图分类号:

TP391

孟磊, 冶忠林, 赵海兴, 杨燕琳. 超网络模型构建中优先连接方法研究[J]. 计算机工程, 2020, 46(10): 103-111.

MENG Lei, YE Zhonglin, ZHAO Haixing, YANG Yanlin. Research on Preferential Connection Method in Construction of Hypernetwork Model[J]. Computer Engineering, 2020, 46(10): 103-111.

https://www.ecice06.com/CN/Y2020/V46/I10/103

图/表 10

20201023091841

20201023091845

20201023091848

20201023091851

20201023091855

20201023091858

20201023091901

20201023091905

20201023091908

20201023091912

参考文献

[1] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.
[2] BARABÁSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[3] SUN Xijing,SI Shoukui.Complex network algorithms and applications[M].Beijing:National Defense Industry Press,2015:1-4.(in Chinese)孙玺菁,司守奎.复杂网络算法与应用[M].北京:国防工业出版社,2015:1-4.
[4] WANG Zhiping,WANG Zhongtuo.Super network theory and its application[M].Beijing:Science Press,2008.(in Chinese)王志平,王众托.超网络理论及其应用[M].北京:科学出版社,2008.
[5] LÜ L,MEDO M,YEUNG C H,et al.Recommender systems[J].Physics Reports,2012,519(1):1-49.
[6] GHOSHAL G,ZLATIC V,CALDARELLI G,et al.Random hypergraphs and their applications[J].Physical Review E-Statistical,Nonlinear,and Soft Matter Physic,2009,79(6):1-11.
[7] BERGE C.Hypergraphs-combinatorics of finite sets[M].New York,USA:Elsevier,1989:1-39.
[8] BERGE C.Graphs and hypergraphs[M].New York,USA:Elsevier,1973:389-413.
[9] WANG Jianwei,RONG Lili,DENG Qiuhong,et al.Evolving hypernetwork model[J].The European Physical Journal B,2010,77(4):493-498.
[10] HU Feng,ZHAO Haixing,MA Xiujuan.An evolving hypernetwork model and its properties[J].Scientia Sinica Physica,Mechanica & Astronomica,2013,43(1):16-22.(in Chinese)胡枫,赵海兴,马秀娟.一种超网络演化模型构建及特性分析[J].中国科学(物理学力学天文学),2013,43(1):16-22.
[11] GUO Jinli,ZHU Xinyun.Emergence of scaling in hypernetworks[J].Acta Physica Sinica,2014,63(9):47-53.(in Chinese)郭进利,祝昕昀.超网络中标度律的涌现[J].物理学报,2014,63(9):47-53.
[12] LIU Yan,ZHANG Qing,YANG Zhengquan,et al.A new evolving model for hypergraph-structure-based complex networks[J].Computer Simulation,2015,32(7):311-314.(in Chinese)刘艳,张青,杨正全,等.一种基于超图复杂网络的新的演化模型[J].计算机仿真,2015,32(7):311-314.
[13] GUO Jinli.Emergence of scaling in non-uniform hyp ernetworks-does "the rich get richer" lead to a power-law distribution?[J].Acta Physica Sinica,2014,63(20):398-403.(in Chinese)郭进利.非均齐超网络中标度律的涌现——富者愈富导致幂律分布吗?[J].物理学报,2014,63(20):398-403.
[14] SUO Qi,GUO Jinli,SUN Shiwei,et al.Exploring the evolutionary mechanism of complex supply chain systems using evolving hypergraphs[J].Physica A:Statistical Mechanics and Its Applications,2018,489:141-148.
[15] HU Feng,ZHAO Haixing,HE Jiabei,et al.An evolving model for hypergraph-structure-based scientific collaboration networks[J].Acta Physica Sinica,2013,62(19):539-546.(in Chinese)胡枫,赵海兴,何佳倍,等.基于超图结构的科研合作网络演化模型[J].物理学报,2013,62(19):539-546.
[16] LI Mengna,GUO Jinli,BIAN Wen,et al.Tang poetry from the perspective of network[J].Complex Systems and Complexity Science,2017,14(4):66-71.(in Chinese)李甍娜,郭进利,卞闻,等.网络视角下的唐诗[J].复杂系统与复杂性科学,2017,14(4):66-71.
[17] HU Feng,LIU Meng,ZHAO Jing,et al.Analysis and application of the topological properties of protein complex hypernetworks[J].Complex Systems and Complexity Science,2018,15(4):31-38.(in Chinese)胡枫,刘猛,赵静,等.蛋白复合物超网络特性分析及应用[J].复杂系统与复杂性科学,2018,15(4):31-38.
[18] DENNING P J.The science of computing:what is computer science[J].American Scientist,1985,73(1):16-19.
[19] NAGURNEY A,DONG J.Supernetworks:decision-making for the information age[M].Cheotenham:Edward Elgar Publishing,2002.
[20] ESTRADA E,RODRÍGUEZ-VELÁZQUEZ J A.Subgraph centrality in complex networks[J].Physical Review E-Statistical,Nonlinear,and Soft Matter Physic,2005,71(5):1-29.
[21] HU Feng.Research on structure,modeling and application of complex supernet[D].Xi'an:Shaanxi Normal University,2014.(in Chinese)胡枫.复杂超网络的结构、建模及应用研究[D].西安:陕西师范大学,2014.

选择文件类型/文献管理软件名称

选择包含的内容

超网络模型构建中优先连接方法研究

Research on Preferential Connection Method in Construction of Hypernetwork Model

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[2]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[3]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[4]	刘迪洋, 张震, 张进. 基于社区结构的复杂网络鲁棒性优化策略[J]. 计算机工程, 2021, 47(8): 84-92.
[5]	吕少卿, 赵雪莉, 张潘, 任新成. 一种保留社区结构信息的网络嵌入算法[J]. 计算机工程, 2021, 47(12): 122-130.
[6]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[7]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[8]	邱少明, 於涛, 杜秀丽, 陈波. 基于节点多属性相似性聚类的社团划分算法[J]. 计算机工程, 2020, 46(7): 84-90,97.
[9]	张志敏, 柴变芳, 李文斌. 基于稀疏自编码器的属性网络嵌入算法[J]. 计算机工程, 2020, 46(7): 98-103,109.
[10]	王曙燕, 韩雪, 孙家泽. 基于风险轨迹与复杂网络的缺陷定位方法[J]. 计算机工程, 2020, 46(6): 202-208.
[11]	谢菁, 羿舒文, 张毅. 基于双曲空间嵌入的极小值社区划分算法[J]. 计算机工程, 2020, 46(6): 73-80.
[12]	朱江, 包崇明, 王崇云, 周丽华, 孔兵. 基于图结构特征分析的Top-k结构洞发现算法[J]. 计算机工程, 2020, 46(5): 94-101,108.
[13]	吴涛, 任淑霞, 张书博. 基于三角形子图的复杂网络过滤压缩算法[J]. 计算机工程, 2020, 46(5): 70-77.
[14]	陆圣宇, 欧锋, 黄清元, 刘宝, 路振民, 汤凌韬. 基于资源分配与偏好连接的局部路径链路预测算法[J]. 计算机工程, 2019, 45(9): 316-320.
[15]	高秀娥, 陈小双, 王运明, 陈波. 基于桥接系数的指挥控制网络桥边识别方法[J]. 计算机工程, 2019, 45(7): 309-314.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

超网络模型构建中优先连接方法研究

Research on Preferential Connection Method in Construction of Hypernetwork Model

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献

相关文章 15

编辑推荐

Metrics

本文评价