Centralization in Small Graphs Öffentlichkeit
Mehta, Cyra Christina (2014)
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
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Stichwort | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
Centralization in Small Graphs () | 2018-08-28 10:37:09 -0400 |
|