The Wayback Machine - https://web.archive.org/web/20221028223521/https://baike.sogou.com/kexue/d10384.htm

网络理论

编辑
一个包含八个顶点和十条边的小型示例网络

网络理论是对离散对象之间对称关系或非对称关系的表示图的研究。在计算机科学和网络科学中,网络理论是图论的一部分:网络可以被定义为节点和/或边具有属性(例如名称)的图。

网络理论在许多学科中都有应用,包括统计物理学、粒子物理学、计算机科学、电气工程[1][2]、生物学、[3]经济学、金融学、运筹学、气候学、生态学和社会学。网络理论的应用包括物流网络、万维网、互联网、基因调控网络、代谢网络、社交网络、认识论网络等。

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

1 网络优化编辑

Break down a NP-hard network optimization task into subtasks by discarding of the most irrelevant interactions in network.[1]

涉及寻找一种最佳的方法去做某事的网络问题被称为组合优化。例如网络流、最短路径问题、运输问题、转运问题、位置问题、匹配问题、分配问题、包装问题、路由问题、关键路径分析和程序评审技术(PERT)。为了将网络优化的NP-hard任务分解成子任务,网络会被分解成相对独立的子网。[5]

2 网络分析编辑

2.1 电网分析

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

(1)抽象视角(即将其看作由节点和边组成的图),而不考虑电力方面的东西(例如,传输线阻抗)。这些研究大多只关注于使用节点度分布和介数分布的电网抽象结构,能够带来关于电网脆弱性评估的实质性见解。通过这些类型的研究,可以从复杂网络的角度(例如,单尺度、无尺度)识别网格结构的类别。这种分类可能在规划阶段或升级基础设施(例如,添加新的输电线路)时有助于电力系统工程师,使输电系统维持一个适当的冗余水平。[1]

(2)表示复杂网络理论和电力系统特性的混合抽象理解的加权图。[2]

2.2 社交网络分析

社交网络分析的可视化[3]

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

自20世纪70年代以来,网络的实证研究在社会科学中发挥了核心作用,许多用于研究网络的数学和统计工具最初也是在社会学中发展起来的。[8] 在许多其他应用中,社交网络分析被用来理解改革、新闻和谣言的传播。同样,它也被用来检查疾病和健康相关行为的传播。它还被应用于市场研究,即被用来考察信任在交换关系中的作用,以及社会机制在定价中的作用。同样,它也被用于研究政治运动和社会组织中的招募活动。它还被用来概念化科学分歧和学术声望。最近,网络分析(以及和其相近的流量分析)在军事情报中获得了重要的应用,用于揭露等级制和无领导性质的叛乱网络。

2.3 生物网络分析

随着最近可公开获得的高通量的生物数据量激增,分子网络的分析已经得到了极大的关注[9]。这种场景下的分析与社交网络的分析密切相关,但通常侧重于网络中的局部模式。例如,网络主题是在网络中特别具有代表性的小子图。类似地,活动主题是网络中节点和边缘属性的模式,在给定网络结构的情况下,这些模式被特别地表示出来。使用网络来分析生物系统中的模式,例如食物网,可以让我们将物种间相互作用的性质和强度进行可视化。针对疾病的生物网络分析推动了网络医学领域的发展[10]。网络理论在生物学中应用的最新例子包括理解细胞周期的应用[11]。大脑、心脏、眼睛等生理系统之间的相互作用,可以被视为一个生理网络。[12]

2.4 叙事网络分析

2012年美国大选的叙事网络[10]

文本语料库的自动解析实现了参与者及其关系网络的大规模提取。由此产生的叙事网络可以包含数千个节点,然后利用网络理论中的工具对其进行分析,以确定关键行为者、关键社区或团体,以及总体网络的健壮性或结构稳定性或某些节点的中心性等一般属性[14]。这使量化叙事分析[15]引入的方法变得自动化,通过这种方法,主语-动词-宾语三元组被识别为由一个动作连接的一对行动者,或者由行动者-宾语形成的一对行动者。[13]

2.5 链分析

链接分析是网络分析的一个子集,探索对象之间的关联。例如,作为警方调查的一部分,可以检查嫌疑人和受害者的地址、他们拨打的电话号码和他们在给定时间内参与的金融交易,以及这些主体之间的家庭关系。这里的链接分析提供了许多不同类型的对象之间的重要关系和关联,这些对象在孤立的信息片段中并不明显。计算机辅助的或全自动的基于计算机的链接分析被越来越多地使用于:银行和保险机构的欺诈检测,电信运营商的电信网络分析,医疗部门的流行病学和药理学,执法调查,用搜索引擎进行相关性评级(反过来,垃圾邮件发送者进行垃圾邮件索引,企业主使用搜索引擎来优化),以及越来越多的其他必须分析许多对象之间关系的地方。链接也来源于两个节点中时间行为的相似性。例如,气候网络中两个地点(节点)之间的联系会由例如两个地点的降雨量或温度波动的相似性来确定。[16][17][18]

网络健壮性

目前正在用渗透理论研究网络的结构鲁棒性。[19] 当节点(或链路)的关键部分被移除时,网络会被分割成小的、断开的集群。这种现象被称为逾渗,[20] 它代表了具有临界指数的有序-无序型相变。逾渗理论可以预测最大组分(称为巨组分)的大小、临界逾渗阈值和临界指数。例如用逾渗理论预测生物病毒壳(衣壳)的破碎,用实验方法预测和检测乙型肝炎病毒衣壳的逾渗阈值:一个分子,在菱形平铺球体上随机玩耶格(Jenga)游戏。 [21] [22]

网络链接分析

一些网络搜索排名算法使用基于链接的中心性度量,包括谷歌的PageRank、克莱因伯格的HITS算法、CheiRank和TrustRank算法。在信息科学和通信科学中也进行链接分析,以便从网页集合的结构中理解和提取信息。例如,可以分析政客网站或博客之间的相互联系。另一个用途是根据页面在其他页面中被提及的情况来对页面进行分类。[23]

2.6 中心性度量

关于图中节点和边的相对重要性的信息可以通过中心性度量来获得,这在社会学等学科中被广泛使用。例如,特征向量中心性使用对应于网络的邻接矩阵的特征向量来确定那些倾向于被频繁访问的节点。正式确定的中心性度量指标包括度中心性、接近中心性、中间中心性、特征向量中心性、子图中心性和卡兹中心性。分析的目的或目标通常决定了要使用的中心性度量的类型。例如,如果人们对网络上的动态情况或网络对节点/链路移除的鲁棒性感兴趣,则节点的动态重要性[24] 是最相关的中心性度量指标。有关基于k-core分析的中心性度量,请参见参考文献。[25]

2.7 相配和异配混合

这些概念用于描述网络中枢纽的链接偏好。枢纽是具有大量链路的节点。一些枢纽倾向于连接到其他枢纽,而另一些则避免连接到枢纽,它们更喜欢连接到连接性低的节点。当一个枢纽倾向于连接到其他枢纽时,我们说它是相配的。分离式枢纽避免连接到其他枢纽。如果枢纽与预期的随机概率有联系,则它们被称为中性的。有三种方法可以量化程度相关性。

2.8 递归网络

递归图的递归矩阵可以看作是无向无权网络的邻接矩阵。这允许了通过网络测量来分析时间序列。应用范围从检测政权变化的动态表征到同步分析。[26][27][28]

3 传播编辑

复杂网络中的内容可以通过两种主要方法传播:保守传播和非保守传播。[29] 在保守传播中,进入复杂网络的内容总量在通过时保持不变。可用一个水罐作为保守传播的模型的最佳形容,水罐里有一定量的水被倒入一系列由管子连接的漏斗中。在这里,水罐代表最初的源头,水代表被传播的内容。漏斗和连接管分别代表节点和节点之间的连接。当水从一个漏斗流入另一个漏斗时,水立即从先前和水接触的漏斗中消失。在非保守传播中,内容的数量随着它进入和通过复杂的网络而变化。非保守扩散模型可形容为一个连续运行的水龙头,水龙头通过一系列由管子连接的漏斗来运行。在这里,来自原始水源的水量是无限的。此外,任何和水接触的漏斗,即使在水进入连续的漏斗时,也会继续让水经过。非保守模型最适合解释大多数传染病、神经兴奋、信息和谣言等的传播过程。

4 相互依赖的网络编辑

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

参考文献

  • [1]

    ^Saleh, Mahmoud; Esa, Yusef; Mohamed, Ahmed (2018-05-29). "Applications of Complex Network Analysis in Electric Power Systems". Energies (in 英语). 11 (6): 1381. doi:10.3390/en11061381..

  • [2]

    ^Saleh, Mahmoud; Esa, Yusef; Onuorah, Nwabueze; Mohamed, Ahmed A. (2017). "Optimal microgrids placement in electric distribution systems using complex network framework". Optimal microgrids placement in electric distribution systems using complex network framework - IEEE Conference Publication. ieeexplore.ieee.org (in 英语). pp. 1036–1040. doi:10.1109/ICRERA.2017.8191215. ISBN 978-1-5386-2095-3. Retrieved 2018-06-07..

  • [3]

    ^Habibi, Iman; Emamian, Effat S.; Abdi, Ali (2014-01-01). "Quantitative analysis of intracellular communication and signaling errors in signaling networks". BMC Systems Biology. 8: 89. doi:10.1186/s12918-014-0089-z. ISSN 1752-0509. PMC 4255782. PMID 25115405..

  • [4]

    ^Newman, M. E. J. "The structure and function of complex networks" (PDF). Department of Physics, University of Michigan..

  • [5]

    ^Ignatov, D.Yu.; Filippov, A.N.; Ignatov, A.D.; Zhang, X. (2016). "Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks". Proc. ISP RAS. 28 (6): 141–152. arXiv:1701.06595. doi:10.15514/ISPRAS-2016-28(6)-10..

  • [6]

    ^Grandjean, Martin (2014). "La connaissance est un réseau". Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166/lcn.10.3.37-54. Retrieved 2014-10-15..

  • [7]

    ^Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. Rainie, Lee and 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 (2014-10-07). "Advanced Fault Diagnosis Methods in Molecular Networks". PLOS ONE. 9 (10): e108830. Bibcode:2014PLoSO...9j8830H. doi:10.1371/journal.pone.0108830. ISSN 1932-6203. PMC 4188586. PMID 25290670..

  • [10]

    ^Barabási, A. L.; Gulbahce, N.; Loscalzo, J. (2011). "Network medicine: a network-based approach to human disease". Nature Reviews Genetics. 12 (1): 56–68. doi:10.1038/nrg2918. PMC 3140052. PMID 21164525..

  • [11]

    ^Jailkhani, N.; Ravichandran, N.; Hegde, S. R.; Siddiqui, Z.; Mande, S. C.; Rao, K. V. (2011). "Delineation of key regulatory elements identifies points of vulnerability in the mitogen-activated signaling network". Genome Research. 21 (12): 2067–81. doi:10.1101/gr.116145.110. PMC 3227097. PMID 21865350..

  • [12]

    ^Bashan, Amir; Bartsch, Ronny P.; Kantelhardt, Jan. W.; Havlin, Shlomo; Ivanov, Plamen Ch. (2012). "Network physiology reveals relations between network topology and physiological function". Nature Communications. 3: 702. arXiv:1203.0242. Bibcode:2012NatCo...3E.702B. doi:10.1038/ncomms1705. ISSN 2041-1723. PMC 3518900. PMID 22426223..

  • [13]

    ^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. (2006). "What Do Networks Have to Do with Climate?". Bulletin of the American Meteorological Society. 87 (5): 585–595. Bibcode:2006BAMS...87..585T. doi:10.1175/BAMS-87-5-585. ISSN 0003-0007..

  • [17]

    ^Yamasaki, K.; Gozolchiani, A.; Havlin, S. (2008). "Climate Networks around the Globe are Significantly Affected by El Niño". Physical Review Letters. 100 (22): 228501. Bibcode:2008PhRvL.100v8501Y. doi:10.1103/PhysRevLett.100.228501. ISSN 0031-9007. PMID 18643467..

  • [18]

    ^Boers, N.; Bookhagen, B.; Barbosa, H.M.J.; Marwan, N.; Kurths, J. (2014). "Prediction of extreme floods in the eastern Central Andes based on a complex networks approach". Nature Communications. 5: 5199. Bibcode:2014NatCo...5E5199B. doi:10.1038/ncomms6199. ISSN 2041-1723. PMID 25310906..

  • [19]

    ^R. Cohen; S. Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press..

  • [20]

    ^A. Bunde; S. Havlin (1996). Fractals and Disordered Systems. Springer..

  • [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 (1998). "Categorization by Context" (PDF). Journal of Universal Computer Science. 4 (9): 719–736..

  • [24]

    ^Restrepo, Juan; E. Ott; B. R. Hunt (2006). "Characterizing the Dynamical Importance of Network Nodes and Links". Phys. Rev. Lett. 97 (9): 094102. arXiv:cond-mat/0606122. Bibcode:2006PhRvL..97i4102R. doi:10.1103/PhysRevLett.97.094102. PMID 17026366..

  • [25]

    ^Carmi, S.; Havlin, S.; Kirkpatrick, S.; Shavitt, Y.; Shir, E. (2007). "A model of Internet topology using k-shell decomposition". Proceedings of the National Academy of Sciences. 104 (27): 11150–11154. arXiv:cs/0607080. Bibcode:2007PNAS..10411150C. doi:10.1073/pnas.0701175104. ISSN 0027-8424. PMC 1896135. PMID 17586683..

  • [26]

    ^Marwan, N.; Donges, J.F.; Zou, Y.; Donner, R.V.; Kurths, J. (2009). "Complex network approach for recurrence analysis of time series". Physics Letters A. 373 (46): 4246–4254. arXiv:0907.3368. Bibcode:2009PhLA..373.4246M. doi:10.1016/j.physleta.2009.09.042. ISSN 0375-9601..

  • [27]

    ^Donner, R.V.; Heitzig, J.; Donges, J.F.; Zou, Y.; Marwan, N.; Kurths, J. (2011). "The Geometry of Chaotic Dynamics – A Complex Network Perspective". European Physical Journal B. 84 (4): 653–672. arXiv:1102.1853. Bibcode:2011EPJB...84..653D. doi:10.1140/epjb/e2011-10899-1. ISSN 1434-6036..

  • [28]

    ^Feldhoff, J.H.; Donner, R.V.; Donges, J.F.; Marwan, N.; Kurths, J. (2013). "Geometric signature of complex synchronisation scenarios". Europhysics Letters. 102 (3): 30007. arXiv:1301.0806. Bibcode:2013EL....10230007F. doi:10.1209/0295-5075/102/30007. ISSN 1286-4854..

  • [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 (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–28. arXiv:0907.1182. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559..

  • [31]

    ^Jianxi Gao; Sergey V. Buldyrev; Shlomo Havlin; H. Eugene Stanley (2011). "Robustness of a Network of Networks". Phys. Rev. Lett. 107 (19): 195701. arXiv:1010.5829. Bibcode:2011PhRvL.107s5701G. doi:10.1103/PhysRevLett.107.195701. PMID 22181627..

阅读 308
版本记录
  • 暂无