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

Thumbnail Title Date Uploaded Actions
Centralization in Small Graphs () 2018-08-28 10:37:09 -0400

Supplemental Files

Thumbnail Title Date Uploaded Actions
PredictCloseCentStar.mov () 2018-08-28 11:49:00 -0400
NoCentvsCumClustInfThreshBetween30_20.mov () 2018-08-28 11:50:48 -0400
OneStarHistCentDegree.mov () 2018-08-28 11:53:12 -0400
OneStarHistCentBetween.mov () 2018-08-28 11:54:34 -0400
PlotCityCationDegree.mov () 2018-08-28 11:56:06 -0400
newCentvsCumClustInfThreshDegreeExtreme.mov () 2018-08-28 11:57:29 -0400
PlotCationRankClose.mov () 2018-08-28 11:58:57 -0400
NoCentvsClustInfThreshCentDegree30_20.mov () 2018-08-28 12:00:23 -0400
ConnectCentvsCumClustInfThreshRanClose30_20.mov () 2018-08-28 12:01:48 -0400
ConnectCentvsClustInfThreshCentClose30_20.mov () 2018-08-28 12:04:35 -0400
AvgDegree.mov () 2018-08-28 12:06:48 -0400
GoodBarSepBetweenness.mov () 2018-08-28 12:08:13 -0400
newCentvsClustInfThreshClose30_20.mov () 2018-08-28 12:09:49 -0400
NoCentvsCumClustInfThreshCentDegree30_20.mov () 2018-08-28 12:11:18 -0400
NoCentvsCumClustInfThreshRanDegree30_20.mov () 2018-08-28 12:13:21 -0400
NoCentvsClustInfThreshBetween30_20.mov () 2018-08-28 12:14:36 -0400
newCentvsCumClustInfThreshClose30_20.mov () 2018-08-28 12:16:24 -0400
ConnectCentvsClustInfThreshRanClose30_20.mov () 2018-08-28 12:18:42 -0400
ConnectCentvsClustInfThreshClose30_20.mov () 2018-08-28 12:20:13 -0400
FlipStarTrimPredLineCationClose.mov () 2018-08-28 12:21:51 -0400
NoCentvsClustInfThreshRanDegree30_20.mov () 2018-08-28 12:23:26 -0400
newCentvsClustInfThreshDegreeExtreme.mov () 2018-08-28 12:24:49 -0400
FlipCDCorrRStatPred.mov () 2018-08-28 12:25:55 -0400
newCentvsCumClustInfThreshRanClose30_20.mov () 2018-08-28 12:27:04 -0400
PredictBetweenCentStar.mov () 2018-08-28 12:28:06 -0400
newCentvsClustInfThreshCentClose30_20.mov () 2018-08-28 12:29:17 -0400
AvgBetweenness.mov () 2018-08-28 12:31:37 -0400
FlipStarTrimPredLineCationBetween.mov () 2018-08-28 12:33:06 -0400
newCentvsCumClustInfThreshCentDegreeExtreme.mov () 2018-08-28 12:34:49 -0400
StarTrimPredMeanCationBetween.mov () 2018-08-28 12:37:27 -0400
StarTrimPredMeanCationClose.mov () 2018-08-28 12:38:59 -0400
newCentvsCumClustInfThreshCentClose30_20.mov () 2018-08-28 12:40:34 -0400
AllCentStarNoOp.mov () 2018-08-28 12:42:00 -0400
AvgCloseness.mov () 2018-08-28 12:43:25 -0400
StarPrefCloseCentCat.mov () 2018-08-28 12:45:23 -0400
NoCentvsCumClustInfThreshCentBetween30_20.mov () 2018-08-28 12:47:02 -0400
CBCorr.mov () 2018-08-28 12:48:24 -0400
FlipStarTrimPredLineCationDegree.mov () 2018-08-28 12:49:57 -0400
Betweenness.mov () 2018-08-28 12:51:27 -0400
OneStarHistCentClose.mov () 2018-08-28 12:52:59 -0400
PlotCityCationBetween.mov () 2018-08-28 12:54:26 -0400
newCentvsClustInfThreshRanDegreeExtreme.mov () 2018-08-28 12:55:54 -0400
CDCorr.mov () 2018-08-28 12:57:27 -0400
AllBarSepDegree.mov () 2018-08-28 12:58:51 -0400
FlipDBCorrRStatPred.mov () 2018-08-28 13:00:14 -0400
AllBarSepBetweenness.mov () 2018-08-28 13:01:49 -0400
ConnectCentvsCumClustInfThreshClose30_20.mov () 2018-08-28 13:03:21 -0400
PlotCityCationClose.mov () 2018-08-28 13:04:46 -0400
ClosenessImp.mov () 2018-08-28 13:06:46 -0400
NoCentvsClustInfThreshCentBetween30_20.mov () 2018-08-28 13:09:17 -0400
GoodBarSepDegree.mov () 2018-08-28 13:10:03 -0400
CentCat.mov () 2018-08-28 13:11:13 -0400
PredictDegreeCentStar.mov () 2018-08-28 13:12:42 -0400
StarTrimPredMeanCationDegree.mov () 2018-08-28 13:14:12 -0400
PlotCationRankDegree.mov () 2018-08-28 13:15:46 -0400
newCentvsClustInfThreshRanClose30_20.mov () 2018-08-28 13:18:53 -0400
AllBarSepCloseness.mov () 2018-08-28 13:19:38 -0400
ConnectCentvsCumClustInfThreshCentClose30_20.mov () 2018-08-28 13:21:25 -0400
StarPrefBetweenCentCat.mov () 2018-08-28 13:23:42 -0400
NoCentvsClustInfThreshDegree30_20.mov () 2018-08-28 13:24:53 -0400
GoodBarSepCloseness.mov () 2018-08-28 13:26:12 -0400
PlotCationRankBetween.mov () 2018-08-28 13:27:15 -0400
NoCentvsCumClustInfThreshDegree30_20.mov () 2018-08-28 13:30:10 -0400
Degree.mov () 2018-08-28 13:31:42 -0400
NoCentvsClustInfThreshRanBetween30_20.mov () 2018-08-28 13:33:16 -0400
BDCorr.mov () 2018-08-28 13:34:40 -0400
newCentvsClustInfThreshCentDegreeExtreme.mov () 2018-08-28 13:36:10 -0400
ConnectStarHistCentClose.mov () 2018-08-28 13:38:21 -0400
NoCentvsCumClustInfThreshRanBetween30_20.mov () 2018-08-28 13:39:36 -0400
StarPrefDegreeCentCat.mov () 2018-08-28 13:41:10 -0400
newCentvsCumClustInfThreshRanDegreeExtreme.mov () 2018-08-28 13:42:43 -0400