大规模网络总体通讯性及其效率评价分析

摘要/Abstract

摘要： 复杂网络中心性测度一直是复杂网络研究的热点,本研究重点关注利用网络邻接矩阵的函数行的和来研究网络总体通讯性的概念。研究的重点包括矩阵指数和解析度,它们在图的路径方面具有天然的解释,研究表明,即使在大型网络中,所提方法也可以非常快速地计算它们。此外,提出节点的通信总和作为网络连接的有效测度,能够测算每个节点与网络的其他节点的通信程度。利用虚拟网络数据和真实数据将总体通讯性中心性度量与相关方法进行比较,结果表明总体通讯性能够有效地作为连通性的整体指标来衡量网络上的信息流动性,具有广泛的应用前景。

关键词: 复杂网络, 通信性, 网络分析, 中心性

Abstract: The centrality measure of nodes has always been a hot topic in complex network research.This paper focused on researching the concept of total communication through the sum of the functions of the network adjacency matrix.The main research includes matrix exponent and resolution,which have natural explanations on the path of the basic graph.The research proved that they can be calculated very quickly even in the case of large networks.In addition,this paper proposed the sum of the node communication as a valid measure of the network connection,which can measure the degree of communication between each node and other nodes in the network.A comparison has been made between the centrality measure of nodes and the related methods by using virtual network data and real data.The results show that the total communication capability can be used as a measure of connectivity for the overall measure of information flow on a given network,which has broad application prospects.

Key words: Centrality, Communication, Complex network, Network analysis

中图分类号:

TP393

闫佳琪, 陈俊华冷晶. 大规模网络总体通讯性及其效率评价分析[J]. 计算机科学, 2018, 45(6A): 283-289. https://doi.org/

YAN Jia-qi, CHEN Jun-hua, LENG Jing. Total Communication and Efficiency Analysis of Large Scale Networks[J]. Computer Science, 2018, 45(6A): 283-289. https://doi.org/

参考文献

[1]CALDARELLI G.Scale-Free Networks[M].UK:Oxford University Press,2007. [2]CROFOOT M C,RUBENSTEIN D I,MAIYA A S,et al.Aggression,grooming and group-level cooperation in white-faced capuchins (Cebus capucinus):Insights from social networks[J].Amer.J.Primatol,2011,73(8):821. [3]ESTRADA E.The Structure of Complex Networks[M].UK: Oxford University Press,2011. [4]ESTRADA E,FOX M,HIGHAM D,et al.Network Science.Complexity in Nature and Technology[M].New York:Sprin-ger,2010. [5]ESTRADA E,HATANO N,BENZI M.The physics of communicability in complex networks[J].Physics Reports,2012,514(3):89-119. [6]LANGVILLE A N,MEYER C D.Google’s PageRank and Beyond:The Science of Search Engine Rankings[M].Princeton,NJ:Princeton University Press,2006. [7]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256. [8]SAVAS B,DHILLON I.Clustered low rank approximation of graphs in information science appli-cations[C]∥Proceedings of the 2011 SIAM Conference on Data Mining.2011:164-175. [9]BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4／5):175-308. [10]BONACICH P.Power and centrality:a family of measures[J].America Journal of Sociology,1987,92:1170-1182. [11]BRANDES U,ERLEBACH T.Network Analysis:Methodological Foundations,Lecture Notes in Computer Science[M].New York:Springer,2005. [12]LANGVILLE A N,MEYER C D.A survey of eigenvector methods for Web information retrieval[J].SIAM Review,2005,47(1):135-161. [13]NEWMAN M E J.Networks:An Introduction[M].UK:Cam- bridge University Press,2010:174-175. [14]NEWMAN M E J,BARABSI A L,WATTS D J.The Structure and Dynamics of Networks[M].Princeton,NJ:Princeton University Press,2003. [15]BENZI M,ESTRADA E,KLYMKO C.Ranking hubs and authorities using matrix functions[J].Linear Algebra and its Applications,2013,438(5):2447-2474. [16]KATZ L.A new status index derived from socio-metric data analysis[J].Psychometrika,1953,18(11):39-43. [17]KLEINBERG J.Authoritative sources in a hyper-linked envi- ronment[J].Journal of ACM,1999,46(5):604-632. [18]LANGVILLE A N,MEYER C D.Who’s No.1? The Science of Rating and Ranking[M].Princeton,NJ:Princeton University Press,2012. [19]LEMPEL R,MORAN S.The stochastic approach for link-struc- ture analysis (SALSA) and the TKC effect[C]∥Proceedings of the Ninth International Conference on the World Wide Web.2000:387-401. [20]ESTRADA E,RODR GUEZ-VELZQUEZ J A.Subgraph centrality in complex networks[J].Physical Review E,2005(55):56-103. [21]ESTRADA E,HIGHAM D J.Network properties revealed through matrix functions[J].SIAM Review,2010,52(4):671-696. [22]BENZI M,BOITO P.Quadrature rule-based bounds for func- tions of adjacency matrices[J].Linear Algebra and its Applications,2010,433(3):637-652. [23]HIGHAM N J.Functions of Matrices:Theory and Computation[M].Philadelphia,PA,USA:Society for Industrial and Applied Mathematics,2008. [24]ESTRADA E,HATANO N.Communicability in complex networks[J].Physical Review E,2008,77(3):036111. [25]BONACICH P,LLOYD P.Eigenvector-like measures of centra- lity for asymmetric relations[J].Social Networks,2001,23(3):191-201. [26]BORGATTI S P,EVERETT M G.A graph-theoretic perspective on centrality[J].Social Networks,2006,28(4):466-484. [27]GRINDROD P,HIGHAM D.A matrix iteration for dynamic network summaries[J].SIAM Review,2013,55(1):118-128. [28]BARABSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[3]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[4]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[6]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[7]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8]	谭琪, 张凤荔, 王婷, 王瑞锦, 周世杰. 融入结构度中心性的社交网络用户影响力评估算法 Social Network User Influence Evaluation Algorithm Integrating Structure Centrality 计算机科学, 2021, 48(7): 124-129. https://doi.org/10.11896/jsjkx.200600096
[9]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[10]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[11]	王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[12]	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[13]	殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[14]	杨旭华, 王晨. 基于网络嵌入与局部合力的复杂网络社区划分算法 Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force 计算机科学, 2021, 48(4): 229-236. https://doi.org/10.11896/jsjkx.200200102
[15]	刘胜久, 李天瑞, 谢鹏, 刘佳. 带权图的多重分形度量 Measure for Multi-fractals of Weighted Graphs 计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed