1. NCCU Academic Hub
  2. Publications
  3. College of Science
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 計算大尺度複雜網路 :以競賽網路及電力網路為例
Computational large-scale complex networks : competition network and power grid
作者 劉彥宏
Liu, Yen Hung
貢獻者 蕭又新
Shiau, Yuo Hsien
劉彥宏
Liu, Yen Hung
關鍵詞 小世界
無尺度度分布
連鎖故障行為
複雜網路
脆弱性分析
small world
scale-free degree distribution
cascading failure
complex network
vulnerability
日期 2011
上傳時間 30-Oct-2012 14:24:34 (UTC+8)
摘要 這篇論文主要可以分成兩個部分。第一部分，我們整理了關於複雜網路的初步研討。最重要的特性有：小世界網路、無尺度度分布。並且介紹了三種模型：BA 模型、EBA模型，以及W-S small world model。接著對於一份實際的社會網路資料—台灣業餘桌球選手對戰網路，做網路的結構分析，試驗其是否具有上述的兩種特性。透過兩種可以模擬出無尺度度分布特性的模型：BA以及EBA模型。我們藉由這兩種模型模擬的結果，以及和競賽網路的比較，試者去闡述模型與理論間為何有些相似，卻又如此不同。並討論了賽制設計對於結構的影響。
在第二部分裡，我們回顧了一些對於網路的拓樸性效率以及可靠度效率的研討，並且討論了兩種不同負載定義下的連鎖故障行為。最後我們使用其中三種方法：拓樸性效率脆弱性、參與中間度(betweenness)過載引發的連鎖性故障行為，以及電力網路的動態電流變化造成的連鎖性故障，對於一個假想的電網做傳輸線的弱點排序。其中由動態電流過載(transient dynamic overload)造成的連鎖性故障可以視為一個簡化後的電力動態網路模型，藉由這三者間排序的不同，我們可以看到複雜網路分析以及基於電力網路傳輸特性所模擬的結果差異。
This thesis can be divided into two parts. In the first part, we review some basic properties of the complex networks. The most important features are: small world networks and scale-free degree distribution. Then, we introduce three complex models : BA model, EBA model, and W-S small world model. Next, we analyze a real data—CTTC network to test if it has the features we have mentioned above. By the EBA and BA model simulations, we try to illustrate why there are some similarities between the simulations and real data, but they are still so different in most of aspects.
In the second part, we review the definitions of the topology and reliable efficiency of a network structure. Next, we discuss two cascading failure model based on different definitions of load of a transmission line in a power grid. Finally, we use three different ways: topology efficiency vulnerability, cascading failure triggered by betweenness overload, and cascading failure triggered by the transient dynamics overload to test the vulnerability of edges in an assuming power grid. The cascading failure triggered by the transient dynamic overload can be viewed as a simplified power flow model. We sort the most vulnerable edges in three different ways. By this, we can observe the difference of the vulnerability analysis based on the complex network and the characteristic of the power transmission..
參考文獻 [1] M.E.J. Newman, A.-L.s. Barabási, D.J. Watts, The structure and dynamics of networks, Princeton University Press, Princeton, 2006.
[2] M.E.J. Newman, Networks : an introduction, Oxford University Press, Oxford ; New York, 2010.
[3] J. Travers, S. Milgram, Experimental Study of Small World Problem, Sociometry, 32 (1969) 425-443.
[4] D.J. Watts, S.H. Strogatz, Collective dynamics of `small-world` networks, Nature, 393 (1998) 440-442.
[5] R. Albert, H. Jeong, A.L. Barabasi, Error and attack tolerance of complex networks, Nature, 406 (2000) 378-382.
[6] A. Motter, Y.-C. Lai, Cascade-based attacks on complex networks, Physical Review E, 66 (2002).
[7] I. Simonsen, L. Buzna, K. Peters, S. Bornholdt, D. Helbing, Transient Dynamics Increasing Network Vulnerability to Cascading Failures, Physical Review Letters, 100 (2008).
[8] K.I. Goh, B. Kahng, D. Kim, Universal Behavior of Load Distribution in Scale-Free Networks, Physical Review Letters, 87 (2001).
[9] E.R.C. Edward .A. Bender, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 24 (1978) 296-307.
[10] I.d.S. Pool, M. Kochen, Contacts and Influence, Social Networks, 1 (1978) 5-51.
[11] B. Uzzi, J. Spiro, Collaboration and creativity: The small world problem, Am J Sociol, 111 (2005) 447-504.
[12] A.L. Barabasi, R. Albert, Emergence of scaling in random networks, Science, 286 (1999) 509-512.
[13] S.H. Strogatz, Exploring complex networks, Nature, 410 (2001) 268-276.
[14] R. Albert, A.L. Barabasi, Topology of evolving networks: local events and universality, Phys Rev Lett, 85 (2000) 5234-5237.
[15] D.J. Watts, S.H. Strogatz, Collective dynamics of `samll-world` networks, Nature, 343 (1998) 440-442.
[16] S. Redner, How popular is your paper? An empirical study of the citation distribution, THE EUROPEAN PHYSICAL JOURNAL B, 4 (1998) 131-134.
[17] D.M. Pennock, G.W. Flake, S. Lawrence, E.J. Glover, C.L. Giles, Winners don`t take all: Characterizing the competition for links on the web, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002) 5207-5211.
[18] O. Sporns, D.R. Chialvo, M. Kaiser, C.C. Hilgetag, Organization, development and function of complex brain networks, Trends Cogn Sci, 8 (2004) 418-425.
[19] C. Li, P.K. Maini, An evolving network model with community structure, JOURNAL OF PHYSICS A: MATHEMATICAL AND GENERAL, 38 (2005) 9741-9749.
[20] V. Latora, M. Marchiori, Efficient Behavior of Small-World Networks, Physical Review Letters, 87 (2001).
[21] I. Eusgeld, W. Kröger, G. Sansavini, M. Schläpfer, E. Zio, The role of network theory and object-oriented modeling within a framework for the vulnerability analysis of critical infrastructures, Reliability Engineering & System Safety, 94 (2009) 954-963.
[22] I. Simonsen, Diffusion and networks: A powerful combination!, Physica A: Statistical Mechanics and its Applications, 357 (2005) 317-330.
[23] S. Arianos, E. Bompard, A. Carbone, F. Xue, Power grid vulnerability: a complex network approach, Chaos, 19 (2009) 013119.
[24] X.Y. Ajendra Dwivedi, Peter Sokolowski, Identifying Vulnerable Lines In a Power Network using Complex Network Theory, IEEE International Symposium on Industrial Electronics (ISlE 2009), (2009).
描述 碩士
國立政治大學
應用物理研究所
98755010
100
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0987550103
資料類型 thesis
dc.contributor.advisor 蕭又新zh_TW
dc.contributor.advisor Shiau, Yuo Hsienen_US
dc.contributor.author (Authors) 劉彥宏zh_TW
dc.contributor.author (Authors) Liu, Yen Hungen_US
dc.creator (作者) 劉彥宏zh_TW
dc.creator (作者) Liu, Yen Hungen_US
dc.date (日期) 2011en_US
dc.date.accessioned 30-Oct-2012 14:24:34 (UTC+8)-
dc.date.available 30-Oct-2012 14:24:34 (UTC+8)-
dc.date.issued (上傳時間) 30-Oct-2012 14:24:34 (UTC+8)-
dc.identifier (Other Identifiers) G0987550103en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54940-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用物理研究所zh_TW
dc.description (描述) 98755010zh_TW
dc.description (描述) 100zh_TW
dc.description.abstract (摘要) 這篇論文主要可以分成兩個部分。第一部分，我們整理了關於複雜網路的初步研討。最重要的特性有：小世界網路、無尺度度分布。並且介紹了三種模型：BA 模型、EBA模型，以及W-S small world model。接著對於一份實際的社會網路資料—台灣業餘桌球選手對戰網路，做網路的結構分析，試驗其是否具有上述的兩種特性。透過兩種可以模擬出無尺度度分布特性的模型：BA以及EBA模型。我們藉由這兩種模型模擬的結果，以及和競賽網路的比較，試者去闡述模型與理論間為何有些相似，卻又如此不同。並討論了賽制設計對於結構的影響。
在第二部分裡，我們回顧了一些對於網路的拓樸性效率以及可靠度效率的研討，並且討論了兩種不同負載定義下的連鎖故障行為。最後我們使用其中三種方法：拓樸性效率脆弱性、參與中間度(betweenness)過載引發的連鎖性故障行為，以及電力網路的動態電流變化造成的連鎖性故障，對於一個假想的電網做傳輸線的弱點排序。其中由動態電流過載(transient dynamic overload)造成的連鎖性故障可以視為一個簡化後的電力動態網路模型，藉由這三者間排序的不同，我們可以看到複雜網路分析以及基於電力網路傳輸特性所模擬的結果差異。		zh_TW
dc.description.abstract (摘要) This thesis can be divided into two parts. In the first part, we review some basic properties of the complex networks. The most important features are: small world networks and scale-free degree distribution. Then, we introduce three complex models : BA model, EBA model, and W-S small world model. Next, we analyze a real data—CTTC network to test if it has the features we have mentioned above. By the EBA and BA model simulations, we try to illustrate why there are some similarities between the simulations and real data, but they are still so different in most of aspects.
In the second part, we review the definitions of the topology and reliable efficiency of a network structure. Next, we discuss two cascading failure model based on different definitions of load of a transmission line in a power grid. Finally, we use three different ways: topology efficiency vulnerability, cascading failure triggered by betweenness overload, and cascading failure triggered by the transient dynamics overload to test the vulnerability of edges in an assuming power grid. The cascading failure triggered by the transient dynamic overload can be viewed as a simplified power flow model. We sort the most vulnerable edges in three different ways. By this, we can observe the difference of the vulnerability analysis based on the complex network and the characteristic of the power transmission..		en_US
dc.description.tableofcontents 1 Introduction 1
1.1 Background 1
2 About the network 5
2.1 Math and tools in the network 5
2.1.1 the basic structures of networks 5
2.1.2 Adjacency matrix 6
2.1.3 Degree and average degree 8
2.1.4 Path and Shortest path 9
2.1.5 Clustering Coefficient 10
2.1.6 Betweenness 11
2.1.7 Components and the largest component 12
2.2 Random network 13
2.2.1 clustering coefficient 13
2.2.2 degree distribution 14
2.2.3 shortest path and the largest component 15
2.2.4 Implementation of random network : shuffle method
and configuration model 17
2.3 Important properties in the real networks 18
2.3.1 high clustering , small world, the small world
quotient (Q) 19
2.3.2 Power-law degree distribution 20
2.4 The models 22
2.4.1 Watts and Strogatz small world model 22
2.4.2 Barabási–Albert model(BA model) 25
2.4.3 Extended BA model (EBA model) 29
2.5 Case study I: CTTC competition network and model
simulations 32
2.5.1 Materials 32
2.5.2 Analysis of real data 33
2.5.3 BA model simulation 37
2.5.4 extend BA model simulation 40
2.5.5 discussion 43
3 Vulnerability and cascading failure of a power grid

3.1 Efficiency 47
3.1.1 topology efficiency 47
3.1.2 reliability efficiency 48
3.1.3 efficiency vulnerability 49
3.2 Cascading failures 50
3.2.1 Betweenness overload 50
3.2.2 transient dynamics 54
3.3 case study II: the imaginary British power grid 62
3.3.1 efficiency vulnerability 62
3.3.2 the cascading failure triggered by the betweenness
overload 64
3.3.3 the cascading failure triggered by the transient
dynamics overload 66
3.4 Discussion 68
4 Conclusion 70

References 72		zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0987550103en_US
dc.subject (關鍵詞) 小世界zh_TW
dc.subject (關鍵詞) 無尺度度分布zh_TW
dc.subject (關鍵詞) 連鎖故障行為zh_TW
dc.subject (關鍵詞) 複雜網路zh_TW
dc.subject (關鍵詞) 脆弱性分析zh_TW
dc.subject (關鍵詞) small worlden_US
dc.subject (關鍵詞) scale-free degree distributionen_US
dc.subject (關鍵詞) cascading failureen_US
dc.subject (關鍵詞) complex networken_US
dc.subject (關鍵詞) vulnerabilityen_US
dc.title (題名) 計算大尺度複雜網路 :以競賽網路及電力網路為例zh_TW
dc.title (題名) Computational large-scale complex networks : competition network and power griden_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] M.E.J. Newman, A.-L.s. Barabási, D.J. Watts, The structure and dynamics of networks, Princeton University Press, Princeton, 2006.
[2] M.E.J. Newman, Networks : an introduction, Oxford University Press, Oxford ; New York, 2010.
[3] J. Travers, S. Milgram, Experimental Study of Small World Problem, Sociometry, 32 (1969) 425-443.
[4] D.J. Watts, S.H. Strogatz, Collective dynamics of `small-world` networks, Nature, 393 (1998) 440-442.
[5] R. Albert, H. Jeong, A.L. Barabasi, Error and attack tolerance of complex networks, Nature, 406 (2000) 378-382.
[6] A. Motter, Y.-C. Lai, Cascade-based attacks on complex networks, Physical Review E, 66 (2002).
[7] I. Simonsen, L. Buzna, K. Peters, S. Bornholdt, D. Helbing, Transient Dynamics Increasing Network Vulnerability to Cascading Failures, Physical Review Letters, 100 (2008).
[8] K.I. Goh, B. Kahng, D. Kim, Universal Behavior of Load Distribution in Scale-Free Networks, Physical Review Letters, 87 (2001).
[9] E.R.C. Edward .A. Bender, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 24 (1978) 296-307.
[10] I.d.S. Pool, M. Kochen, Contacts and Influence, Social Networks, 1 (1978) 5-51.
[11] B. Uzzi, J. Spiro, Collaboration and creativity: The small world problem, Am J Sociol, 111 (2005) 447-504.
[12] A.L. Barabasi, R. Albert, Emergence of scaling in random networks, Science, 286 (1999) 509-512.
[13] S.H. Strogatz, Exploring complex networks, Nature, 410 (2001) 268-276.
[14] R. Albert, A.L. Barabasi, Topology of evolving networks: local events and universality, Phys Rev Lett, 85 (2000) 5234-5237.
[15] D.J. Watts, S.H. Strogatz, Collective dynamics of `samll-world` networks, Nature, 343 (1998) 440-442.
[16] S. Redner, How popular is your paper? An empirical study of the citation distribution, THE EUROPEAN PHYSICAL JOURNAL B, 4 (1998) 131-134.
[17] D.M. Pennock, G.W. Flake, S. Lawrence, E.J. Glover, C.L. Giles, Winners don`t take all: Characterizing the competition for links on the web, Proceedings of the National Academy of Sciences of the United States of America, 99 (2002) 5207-5211.
[18] O. Sporns, D.R. Chialvo, M. Kaiser, C.C. Hilgetag, Organization, development and function of complex brain networks, Trends Cogn Sci, 8 (2004) 418-425.
[19] C. Li, P.K. Maini, An evolving network model with community structure, JOURNAL OF PHYSICS A: MATHEMATICAL AND GENERAL, 38 (2005) 9741-9749.
[20] V. Latora, M. Marchiori, Efficient Behavior of Small-World Networks, Physical Review Letters, 87 (2001).
[21] I. Eusgeld, W. Kröger, G. Sansavini, M. Schläpfer, E. Zio, The role of network theory and object-oriented modeling within a framework for the vulnerability analysis of critical infrastructures, Reliability Engineering & System Safety, 94 (2009) 954-963.
[22] I. Simonsen, Diffusion and networks: A powerful combination!, Physica A: Statistical Mechanics and its Applications, 357 (2005) 317-330.
[23] S. Arianos, E. Bompard, A. Carbone, F. Xue, Power grid vulnerability: a complex network approach, Chaos, 19 (2009) 013119.
[24] X.Y. Ajendra Dwivedi, Peter Sokolowski, Identifying Vulnerable Lines In a Power Network using Complex Network Theory, IEEE International Symposium on Industrial Electronics (ISlE 2009), (2009).		zh_TW