维基百科

网络理论

图论理论

网络理论（Network theory）是一种对图的研究，也是对称关系或不对称关系（英语：Directed graph）在离散对象中的一种表现。 在计算机科学和网络科学中 ，网络理论是图论的一部分：网络可以定义为节点和/或边具有属性（例如名称）的图。

一个有8个顶点与10条边的小型网络示例

网络理论目前在许多学科中有应用，学科包括统计物理学、粒子物理学、计算机科学、电气工程学[1][2]、生物学、[3]经济学、金融学、运筹学、气候学、生态学和社会学；应用包括物流网、万维网、互联网、基因调控网络（英语：Gene regulatory network）、代谢网络、社会网络、知识论网络等。

欧拉对柯尼斯堡七桥问题的解答被认为是在网络理论中第一个被认可的证明。[4]

网络优化

 
通过忽略掉网络中许多不相关的影响作用，将NP困难网络的优化任务分为许多子模块。[5]

在名称组合优化的模块中，人们正在研究涉及到寻找某类事务最优路径的网络问题。 其实例包括 网络流问题、最短路径问题、运输问题（英语：Transport problem）、转运问题（英语：Transshipment problem）、选址问题（英语：Facility location problem）、匹配问题、分配问题、包装问题（英语：Packing problem）、路由问题、关键路径分析与计划评审技术（项目评估与审查技术）。 为了将网络优化的一个NP困难任务分解成子任务。网络被分解为相对独立的子网络[5]

网络分析

电子网络分析

电力系统的分析可以利用网络理论从两个主要角度进行:

1.一个抽象的网络(例如一个图包括节点和边)，不考虑其电力模块(例如传送线路受阻抗影响)。 这些研究大多数集中在抽象电网结构其节点的度与介数的分布上，而该分布引入了关于网格脆弱性评估的实质性见解。通过这些类型的研究，网格结构的类别可以从网络结构的复杂度（例如，单尺度、无尺度）确定。 这种分类可能有助于电力系统工程师在规划阶段或在升级基础设施（例如，增加一条新的输电线路）时保持输电系统的适当冗余水平。[1]

2.掺杂了对复杂网络理论与电力系统特性的抽象理解的加权图。[2]

社会网络分析

 
可视化的社会网络分析[6]

社会网络分析研究社会实体之间的关系结构。[7]这些实体通常是个人，但也可能是团体、组织、国家、网站或学术出版物。

自20世纪70年代以来，对网络的实证研究在社会科学中处于核心地位，许多用于研究网络的数学和统计学工具最早是在社会学中发展起来的。[8]在许多其他应用中，社交网络分析被用来解释创新、新闻和谣言的传播。类似地，它也被用来检测疾病和健康相关行为的传播。在市场研究中，它还被用来研究信任在交换关系中与社会机制在物品定价中的作用。除此以外，它还被用来研究政治运动和社会组织的招新问题，以及被用来将科学分歧和学术声望观念化。最近，网络分析（以及它的近亲流量分析）在军事情报中获得了重要的应用，用于揭露有等级与无领导群体的叛乱网络。

生物网络分析

随着近年来公开的高通量生物数据的激增，分子网络分析引起了人们极大的兴趣。[9]这种背景下的分析类型与社会网络分析密切相关，但更关注网络中的局部模式。例如，网络基元是在网络中被过度表示的小型子图。类似地，活动基元是在给定网络结构中节点和边被过度表示的模块属性。利用网络来分析生物系统的模式，例如食物网，可以让我们看到物种之间相互作用的特征和强度。对疾病生物网络的分析，促进了网络医学的发展。[10]网络理论在生物学中应用的最新例子包括对细胞周期的理解。[11]脑、心、眼等生理系统之间的相互作用可以看作是一个生理网络。[12]

叙事网络分析

 
2012美国选举的叙事网络[13]

语料库的自动解析在很大程度上实现了角色及其关系网络的提取。然后，使用网络理论中的工具分析可产生包含数千个节点的叙事网络，从而确定关键角色、关键社区或团体，并确定其常规属性如总体网络的鲁棒性或结构稳定性，以及某些节点的中心性等。[14]这针对定量叙事分析引入自动化的方法，即主谓宾结构被识别为不同角色由一个动作连接或由一对主宾结构组成。[15][13]

链接分析

链接分析是网络分析的一个子集，其研究对象之间的关联性。例如，作为警方调查的一部分，其可以检查犯罪嫌疑人和受害者的地址、他们拨打的电话号码、他们在特定时间内参与的金融交易，以及这些对象之间的家庭关系。链接分析在此提供了许多不同类型的对象之间的关键关系和关联，而其在独立的信息片段中并不明显。计算机辅助或全自动的链接分析越来越多地被使用在各个方面，其中包括银行和保险机构进行欺诈检测，电信运营商进行电信网络分析，医疗部门进行流行病学和药理学分析以及执法调查，搜索引擎进行相关性评级(也包括垃圾邮件发送者发送垃圾邮件与用户进行搜索引擎优化)，以及其他需要分析许多对象之间关系的地方。链接也取决于两个节点时间行为的相似性。例如，气候网络中两个地点(节点)之间的联系是由两个地点的降雨或温度变化的相似性决定的。[16][17][18]

网络鲁棒性

对网络结构鲁棒性的研究利用了渗流理论。[19]当节点(或链接)的关键部分被删除时，网络就会分裂成小的、不连通的社团。这种现象被称为渗流现象，它代表了临界指数从有序到无序的一种相变类型。[20]渗流理论可以预测最大连通分量(称为超连通分量)的大小、临界渗流阈值和临界指数。其中一个例子是利用渗透理论预测生物病毒壳层(衣壳)的破碎，并通过实验预测并检测乙肝病毒衣壳的渗透阈值:在底边为菱形的范围上随机进行分子量级的堆叠游戏。[21][22]

网络链接分析

一些网络搜索排名算法使用了以链接为中心的衡量指标，包括谷歌的PageRank、Kleinberg的HITS算法、CheiRank（英语：CheiRank）和TrustRank（英语：TrustRank）算法。链接分析也应用于信息科学和通信科学中，从而了解并提取网页结构中的信息。例如，有可能是针对政治家的网站或博客之间相互联系的分析。另一个用途是根据在其他页面中提到的内容对页面进行分类。[23]

中心性测量

图中节点和边的相对重要性的信息可以通过中心性的测量得出，其社会学等学科中得到广泛应用。例如，特征向量中心性利用邻接矩阵针对该网络的特征向量来确定有被频繁访问趋势的节点。正式建立的中心性指标有度中心性、接近中心性、介数中心性、特征向量中心性、子图中心性和Katz中心性。分析的目的或目标通常由使用的中心性测量类型所决定。例如，如果一个人对网络动态或网络在移除节点/边时的鲁棒性感兴趣，通常节点的动态重要性是中心度测量中最相关的参数。[24]基于k-core分析的中心性测量见参考文献。[25]

同型和异型匹配

这些概念用于描述网络中集线器的链接偏好。集线器是具有大量连接的节点。一些集线器倾向于连接到其他集线器，而另一些集线器则避免连接到集线器而倾向于连接到连接性较差的节点。当一个集线器倾向于连接到其他集线器时，其被称为同型集线器。异型集线器则避免连接到其他集线器。如果集线器是处于预期随机概率的则称为中性。有三种方法可以量化其相关性程度。

递归网络

递归图的递归矩阵可以看作是无向无权网络的邻接矩阵。这允许通过网络标准对时间序列进行分析。其应用范围为检测从特征动力学到同步分析的状态变化。[26][27][28]

传播

在复杂网络中的内容可以通过两种主要方式传播:守恒传播与不守恒传播。[29]在守恒传播中，进入复杂网络的内容总量在其通过时保持不变。这种守恒传播模型可以用一个装有水的水罐被倒入由管道连接的漏斗来表示。其中水罐代表源头，水则是正在传播的内容。漏斗和连接管道分别表示节点与这些节点之间的连接。当水从一个漏斗流到另一个漏斗时，先前漏斗中的水会立即消失。在不守恒传播中，内容的数量在其进入和通过复杂网络时发生变化。不守恒传播模型可以用一个连续运行且通过由管道连接的漏斗的水龙头来表示。其中来自水源的水量是无限的。同时，任何接触过水的漏斗，即时在水进入下一个漏斗时，也会继续受到水的影响。不守恒模型非常适用于解释大多数传染病、神经兴奋、信息和谣言等的传播。

相互依赖网络

相互依赖网络是一个耦合网络系统，其中一个或多个网络的节点取决于其他网络中的节点。现代技术的发展增强了这种依赖性。依赖关系可能导致网络之间的级联故障，一个相对较小的失误便可能导致系统的灾难性故障。停电是网络之间的依赖性重要地位的一个有代表性的证明。最近的一项研究开发了一个框架来研究相互依赖的网络系统中的级联故障。[30][31]

相关

参考文献

  1. ^ 1.0 1.1 Saleh, Mahmoud; Esa, Yusef; Mohamed, Ahmed. Applications of Complex Network Analysis in Electric Power Systems. Energies. 2018-05-29, 11 (6): 1381. doi:10.3390/en11061381 （英语）. 
  2. ^ 2.0 2.1 Saleh, Mahmoud; Esa, Yusef; Onuorah, Nwabueze; Mohamed, Ahmed A. Optimal microgrids placement in electric distribution systems using complex network framework. ieeexplore.ieee.org. 2017: 1036–1040 [2018-06-07]. ISBN 978-1-5386-2095-3. doi:10.1109/ICRERA.2017.8191215. （原始内容存档于2021-04-30） （美国英语）. 
  3. ^ Habibi, Iman; Emamian, Effat S.; Abdi, Ali. Quantitative analysis of intracellular communication and signaling errors in signaling networks. BMC Systems Biology. 2014-01-01, 8: 89. ISSN 1752-0509. PMC 4255782  . PMID 25115405. doi:10.1186/s12918-014-0089-z. 
  4. ^ Newman, M. E. J. The structure and function of complex networks (PDF). Department of Physics, University of Michigan. [2019-05-16]. （原始内容存档 (PDF)于2021-03-14）. 
  5. ^ 5.0 5.1 Ignatov, D.Yu.; Filippov, A.N.; Ignatov, A.D.; Zhang, X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks. Proc. ISP RAS. 2016, 28 (6): 141–152. arXiv:1701.06595  . doi:10.15514/ISPRAS-2016-28(6)-10. 
  6. ^ Grandjean, Martin. La connaissance est un réseau. Les Cahiers du Numérique. 2014, 10 (3): 37–54 [2014-10-15]. doi:10.3166/lcn.10.3.37-54. （原始内容存档于2015-06-27）. 
  7. ^ Wasserman, Stanley（英语：Wasserman, Stanley） and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. Rainie, Lee and Barry Wellman（英语：Barry Wellman）, Networked: The New Social Operating System. Cambridge, MA: MIT Press, 2012.
  8. ^ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
  9. ^ Habibi, Iman; Emamian, Effat S.; Abdi, Ali. Advanced Fault Diagnosis Methods in Molecular Networks. PLOS ONE. 2014-10-07, 9 (10): e108830. Bibcode:2014PLoSO...9j8830H. ISSN 1932-6203. PMC 4188586  . PMID 25290670. doi:10.1371/journal.pone.0108830. 
  10. ^ Barabási, A. L.; Gulbahce, N.; Loscalzo, J. Network medicine: a network-based approach to human disease. Nature Reviews Genetics. 2011, 12 (1): 56–68. PMC 3140052  . PMID 21164525. doi:10.1038/nrg2918. 
  11. ^ Jailkhani, N.; Ravichandran, N.; Hegde, S. R.; Siddiqui, Z.; Mande, S. C.; Rao, K. V. Delineation of key regulatory elements identifies points of vulnerability in the mitogen-activated signaling network. Genome Research. 2011, 21 (12): 2067–81. PMC 3227097  . PMID 21865350. doi:10.1101/gr.116145.110. 
  12. ^ Bashan, Amir; Bartsch, Ronny P.; Kantelhardt, Jan. W.; Havlin, Shlomo; Ivanov, Plamen Ch. Network physiology reveals relations between network topology and physiological function. Nature Communications. 2012, 3: 702. Bibcode:2012NatCo...3E.702B. ISSN 2041-1723. PMC 3518900  . PMID 22426223. arXiv:1203.0242  . doi:10.1038/ncomms1705. 
  13. ^ 13.0 13.1 Automated analysis of the US presidential elections using Big Data and network analysis; S Sudhahar, GA Veltri, N Cristianini; Big Data & Society 2 (1), 1–28, 2015
  14. ^ Network analysis of narrative content in large corpora; S Sudhahar, G De Fazio, R Franzosi, N Cristianini; Natural Language Engineering, 1–32, 2013
  15. ^ Quantitative Narrative Analysis; Roberto Franzosi; Emory University © 2010
  16. ^ Tsonis, Anastasios A.; Swanson, Kyle L.; Roebber, Paul J. What Do Networks Have to Do with Climate?. Bulletin of the American Meteorological Society. 2006, 87 (5): 585–595. Bibcode:2006BAMS...87..585T. ISSN 0003-0007. doi:10.1175/BAMS-87-5-585. 
  17. ^ Yamasaki, K.; Gozolchiani, A.; Havlin, S. Climate Networks around the Globe are Significantly Affected by El Niño. Physical Review Letters. 2008, 100 (22): 228501. Bibcode:2008PhRvL.100v8501Y. ISSN 0031-9007. PMID 18643467. doi:10.1103/PhysRevLett.100.228501. 
  18. ^ Boers, N.; Bookhagen, B.; Barbosa, H.M.J.; Marwan, N.; Kurths, J. Prediction of extreme floods in the eastern Central Andes based on a complex networks approach. Nature Communications. 2014, 5: 5199. Bibcode:2014NatCo...5E5199B. ISSN 2041-1723. PMID 25310906. doi:10.1038/ncomms6199. 
  19. ^ R. Cohen; S. Havlin. Complex Networks: Structure, Robustness and Function. Cambridge University Press. 2010 [2019-05-16]. （原始内容存档于2011-10-04）. 
  20. ^ A. Bunde; S. Havlin. Fractals and Disordered Systems. Springer. 1996 [2019-05-16]. （原始内容存档于2020-10-14）. 
  21. ^ Brunk, N. E., Lee, L. S., Glazier, J. A., Butske, W., & Zlotnick, A. (2018). "Molecular Jenga: the percolation phase transition (collapse) in virus capsids". Physical Biology, 15(5), 056005.
  22. ^ Lee, L. S., Brunk, N., Haywood, D. G., Keifer, D., Pierson, E., Kondylis, P., ... & Zlotnick, A. (2017). "A molecular breadboard: Removal and replacement of subunits in a hepatitis B virus capsid （页面存档备份，存于互联网档案馆）". Protein Science, 26(11), 2170-2180.
  23. ^ Attardi, G.; S. Di Marco; D. Salvi. Categorization by Context (PDF). Journal of Universal Computer Science（英语：Journal of Universal Computer Science）. 1998, 4 (9): 719–736 [2019-05-16]. （原始内容存档 (PDF)于2020-10-25）. 
  24. ^ Restrepo, Juan; E. Ott; B. R. Hunt. Characterizing the Dynamical Importance of Network Nodes and Links. Phys. Rev. Lett. 2006, 97 (9): 094102. Bibcode:2006PhRvL..97i4102R. PMID 17026366. arXiv:cond-mat/0606122  . doi:10.1103/PhysRevLett.97.094102. 
  25. ^ Carmi, S.; Havlin, S.; Kirkpatrick, S.; Shavitt, Y.; Shir, E. A model of Internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences. 2007, 104 (27): 11150–11154. Bibcode:2007PNAS..10411150C. ISSN 0027-8424. PMC 1896135  . PMID 17586683. arXiv:cs/0607080  . doi:10.1073/pnas.0701175104. 
  26. ^ Marwan, N.; Donges, J.F.; Zou, Y.; Donner, R.V.; Kurths, J. Complex network approach for recurrence analysis of time series. Physics Letters A. 2009, 373 (46): 4246–4254. Bibcode:2009PhLA..373.4246M. ISSN 0375-9601. arXiv:0907.3368  . doi:10.1016/j.physleta.2009.09.042. 
  27. ^ Donner, R.V.; Heitzig, J.; Donges, J.F.; Zou, Y.; Marwan, N.; Kurths, J. The Geometry of Chaotic Dynamics – A Complex Network Perspective. European Physical Journal B. 2011, 84 (4): 653–672. Bibcode:2011EPJB...84..653D. ISSN 1434-6036. arXiv:1102.1853  . doi:10.1140/epjb/e2011-10899-1. 
  28. ^ Feldhoff, J.H.; Donner, R.V.; Donges, J.F.; Marwan, N.; Kurths, J. Geometric signature of complex synchronisation scenarios. Europhysics Letters. 2013, 102 (3): 30007. Bibcode:2013EL....10230007F. ISSN 1286-4854. arXiv:1301.0806  . doi:10.1209/0295-5075/102/30007. 
  29. ^ Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
  30. ^ S. V. Buldyrev; R. Parshani; G. Paul; H. E. Stanley; S. Havlin. Catastrophic cascade of failures in interdependent networks. Nature. 2010, 464 (7291): 1025–28 [2019-05-16]. Bibcode:2010Natur.464.1025B. PMID 20393559. arXiv:0907.1182  . doi:10.1038/nature08932. （原始内容存档于2017-10-18）. 
  31. ^ Jianxi Gao; Sergey V. Buldyrev; Shlomo Havlin; H. Eugene Stanley. Robustness of a Network of Networks. Phys. Rev. Lett. 2011, 107 (19): 195701 [2019-05-16]. Bibcode:2011PhRvL.107s5701G. PMID 22181627. arXiv:1010.5829  . doi:10.1103/PhysRevLett.107.195701. （原始内容存档于2021-04-15）. 

书籍

  • S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0-19-851590-1
  • G. Caldarelli, "Scale-Free Networks", Oxford University Press, 2007, ISBN 978-0-19-921151-7
  • A. Barrat, M. Barthelemy, A. Vespignani, "Dynamical Processes on Complex Networks", Cambridge University Press, 2008, ISBN 978-0521879507
  • E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011, ISBN 978-0-199-59175-6
  • Kimmo., Soramäki. Network theory and financial risk. Cook, Samantha (Statistician). [London]: Risk Books. 2016. ISBN 978-1782722199. OCLC 973733901. 
  • V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Cambridge University Press, 2017, ISBN 978-1107103184

外部链接

检索自“https://zh.wikipedia.org/w/index.php?title=网络理论&oldid=77813710”