維基百科

網絡理論

图论理论

網絡理論（Network theory）是一種對圖的研究，也是對稱關係或不對稱關係（英語：Directed graph）在離散對象中的一種表現。 在計算機科學和網絡科學中 ，網絡理論是圖論的一部分：網絡可以定義為節點和/或邊具有屬性（例如名稱）的圖。

一個有8個頂點與10條邊的小型網絡示例

網絡理論目前在許多學科中有應用，學科包括統計物理學、粒子物理學、計算機科學、電氣工程學[1][2]、生物學、[3]經濟學、金融學、運籌學、氣候學、生態學和社會學；應用包括物流網、萬維網、互聯網、基因調控網絡（英語：Gene regulatory network）、代謝網絡、社會網絡、知識論網絡等。

歐拉對柯尼斯堡七橋問題的解答被認為是在網絡理論中第一個被認可的證明。[4]

網絡優化

 
通過忽略掉網絡中許多不相關的影響作用，將NP困難網絡的優化任務分為許多子模塊。[5]

在名稱組合優化的模塊中，人們正在研究涉及到尋找某類事務最優路徑的網絡問題。 其實例包括 網絡流問題、最短路徑問題、運輸問題、轉運問題（英語：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"