Centralization in Small Graphs Público

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	Laney Graduate School
Department	Biostatistics
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Biology, Biostatistics
Palavra-chave	SIR Centralization Graph Network
Committee Chair / Thesis Advisor	Hertzberg, Vicki S, Emory University
Committee Members	Hill, Andrew , CDC Haber, Michael J, Emory University Waller, Lance, Emory University Weiss, Howard, Georgia Institute of Technology

Última modificação

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Centralization in Small Graphs ()	2018-08-28 10:37:09 -0400	Press to Select an action Download

Supplemental Files

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