Centralization in Small Graphs 公开

Mehta, Cyra Christina (2014)

Permanent URL: https://etd.library.emory.edu/concern/etds/8s45q890d?locale=zh
Published

Abstract

Network science provides a new and valuable set of techniques for investigating problems by providing a different perspective. One important network characteristic is centralization, which is a quantification of how much one node dominates the network according to a particular measure of node influence. Centralization is a graph-level measure and can be calculated for closeness, betweenness, and degree. This research investigated the range of centralization values obtained by common graph generating methods, properties of centralization, and whether centralization is associated with disease spread. The first study examined the centralization values and graph structures produced by Erdos-Renyi Gnm random graphs, Barabasi-Albert preferential attachment graphs, small world graphs, and two node preferential attachment graphs as well as Star Start, a new graph generating method that produces graphs across the full theoretical range of centralization values. Erdos-Renyi random graphs produce low to moderately centralized graphs and small world graphs are only low to moderately centralized. Barabasi-Albert preferential attachment graphs can be highly centralized but do not produce a variety of graph structures. Two node type preferential attachment and Star Start produce most of the full range of centralization values with a broad range of structures. Using the Star Start program, the second study explored the properties of centralization, including prediction based on average or maximum node centrality. Correlation between centralization measures decreases as graph order increases. Models predicting centralization based on maximum centrality perform reasonably well, especially when the maximum centrality value <0.6. Models based on average centrality fit poorly after the average increases past the average centrality of a star graph. Lastly, the association between centralization and epidemiologic endpoints using a Susceptible-Infected-Recovered (SIR) compartment model of disease spread was examined. As degree or betweenness centralization increases the peak number of infected nodes increases, time until the peak decreases, and the final cumulative number of infected nodes also increases. Closeness centralization does not have as strong of a relationship and should only be considered for connected networks. The results also confirm that infecting the most central node first produces a more severe epidemic than randomly selecting a node.

Table of Contents

I Background............................................................................. 1
1 Introduction........................................................................... 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Closeness Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Closeness Centralization . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Betweenness Centrality . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.4 Betweenness Centralization . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.5 Degree Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.6 Degree centralization . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Literature Review ..................................................................14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Relative Centrality/Centralization Properties . . . . . . . . . . . . . . . . . 14
2.3 Other Centrality Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Eigenvector Centrality . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Other Centralization Measures . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Networks in Public Health . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Network Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Generating Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
II Topic 1 ................................................................................26
3 Centralization in Various Graph Generating Methods................. 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Erd�os-Renyi Random Graphs . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Barabasi-Albert Preferential Attachment . . . . . . . . . . . . . . . 31
3.2.3 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.4 Two Node Type Preferential Attachment . . . . . . . . . . . . . . . 32
3.2.5 Star Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.1 Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.2 Betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.3 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7 Movies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7.1 Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7.2 Betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.7.3 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.8.1 Movies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
III Topic 2 ..........................................................................47
4 Various Properties of Centralization in Small Graphs .................48
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.1 Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Graph Generating Methods . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.2 Comparison of Distributions . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Centralization Associations . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3.1 Comparison of Distributions . . . . . . . . . . . . . . . . . . . . . . . 57
4.3.2 Centralization Associations . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6 Figures, Movies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6.1 Comparison of Distributions . . . . . . . . . . . . . . . . . . . . . . . 65
4.6.2 Centralization Associations . . . . . . . . . . . . . . . . . . . . . . . 66
4.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.7.1 Movies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
IV Topic 3 79
5 Centralization in Disease Spread 80
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.1 Disease Spread in Networks . . . . . . . . . . . . . . . . . . . . . . . 82
5.1.2 Epidemic Threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.1 Graph Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.2 SIR Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.1 Degree Centralization . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.2 Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.3.3 Betweenness Centralization . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6 Figures, Movies, Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6.1 Degree Centralization . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6.2 Closeness Centralization . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.6.3 Betweenness Centralization . . . . . . . . . . . . . . . . . . . . . . . 145
5.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.7.1 Closeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.7.2 Figures, Movies, Tables . . . . . . . . . . . . . . . . . . . . . . . . . 162
V Conclusion .........................................................................181
6 Conclusion .........................................................................182
VI Appendix .........................................................................184
7 A New Method for Creating Centralized Graphs: Star Start ........185
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.2 Star Start Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
7.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.7 Figures, Movies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.8 Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
8 Bibliography........................................................................ 206

About this Dissertation

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
关键词
Committee Chair / Thesis Advisor
Committee Members
最新修改

Primary PDF

Supplemental Files