Centrality and Communicability Measures in Complex Networks: Analysis and Algorithms Público
Klymko, Christine Frances (2014)
Published
Abstract
Complex systems are ubiquitous throughout the world, both in nature and within man-made structures. Over the past decade, large amounts of network data have become available and, correspondingly, the analysis of complex networks has become increasingly important. One of the fundamental questions in this analysis is to determine the most important elements in a given network. Measures of node importance are usually referred to as node centrality, and many centrality measures have been proposed over the years. Here, we focus on the analysis and computation of centrality measures based on matrix functions.
First, we examine a node centrality measure based on the notion of total communicability, defined in terms of the row sums of the exponential of the adjacency matrix of the network. We argue that this is a natural metric for ranking nodes in a network, and we point out that it can be computed very rapidly even in the case of large networks. Furthermore, we propose the total sum of node communicabilities as a useful measure of network connectivity.
Next, we compare various parameterized centrality rankings based on the matrix expo- nential and matrix resolvent with degree and eigenvector centrality. We demonstrate an analytical relationship between these rankings which helps to explain explain the observed robustness of these rankings on many real world networks, even though the scores produced by the centrality measures are not stable.
Finally, we propose an extension of these measures to directed networks, and we apply them to the problem of ranking hubs and authorities. The extension is achieved by bipartization, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities.
Table of Contents
List of Figures xi
List of Tables xv
1 Introduction 3
1.1 Background and motivation
......................... 3
1.1.1
Introduction to complex networks ................. 3
1.1.2 Outline of thesis ........................... 3
1.2 Basic concepts from graph theory...................... 6
1.3 Basic concepts from linear algebra ..................... 9
1.4 Properties of complex networks....................... 13
1.5 Measures of centrality and communicability . . . . . . . . . . . . . . . . 16
1.5.1 HITS.................................. 18
1.5.2 PageRank............................... 20
1.6 Comparing centrality measures ....................... 23
1.7 Approximationsofcentralityscores..................... 24
1.7.1 Approximation of diagonal entries of matrix functions . . . . . . 25
1.7.2 Approximation of row sums of matrix functions . . . . . . . . . . 28
2 Total Communicability as a Centrality Measure 31
2.1 Introduction.................................. 31
2.2 Diagonal entries vs. row sums........................ 32
2.3 Total network communicability ....................... 34
2.4 Computational studies ............................ 37
2.4.1 Test matrices ............................. 38
2.4.2 Total communicability in small world networks . . . . . . . . . . 42
2.4.3 Discussion of test results using synthetic data . . . . . . . . . . . 42
2.4.4 Real data ............................... 44
2.4.5 Identification of essential proteins in PPI network of yeast . . . . 51
2.4.6 Further discussion of test results using real networks . . . . . . . 51
2.5 Computational aspects............................ 53
2.5.1 A large-scale example ........................ 54
2.6 Resolvent-based centrality measures .................... 55
2.7 Summary and conclusions.......................... 62
3 Robustness of Parameterized Centrality Rankings 65
3.1 Introduction.................................. 65
3.2 Relationship between various centrality measures . . . . . . . . . . . . . 66
3.3 Interpretation................................. 69
3.4 A small example ............................... 71
3.5 Numerical Experiments on real data .................... 73
3.5.1 Exponential subgraph centrality and total communicability . . . . 74
3.5.2 Resolvent subgraph and Katz centrality. . . . . . . . . . . . . . . 79
3.6 Centrality robustness in directed networks . . . . . . . . . . . . . . . . . 84
3.7 Numerical experiments on directed networks . . . . . . . . . . . . . . . 88
3.7.1 Total communicability ........................ 88
3.7.2 Katz centrality ............................ 92
3.8 Summary and conclusions.......................... 95
4 Ranking Hubs and Authorities using Matrix Functions 97
4.1 Introduction.................................. 97
4.2 HITS reformulation.............................. 97
4.3 Subgraph centralities and communicabilities . . . . . . . . . . . . . . . . 99
4.4 An extension to digraphs...........................101
4.4.1 Interpretation of diagonal entries..................102
4.4.2 Interpretation of off-diagonal entries . . . . . . . . . . . . . . . . 105
4.4.3 Relationship with HITS .......................107
4.5 Other ranking schemes............................109
4.5.1 Resolvent-based measures......................109
4.5.2 PageRank and Reverse PageRank..................111
4.6 Examples on small digraphs.........................112
4.6.1 Example 1...............................112
4.6.2 Example 2...............................115
4.6.3 Example 3...............................117
4.7 Application to web graphs..........................119
4.7.1 Abortion dataset...........................120
4.7.2 Computational complexity dataset.................122
4.7.3 Death penalty dataset........................124
4.7.4 Stanford web graph .........................126
4.8 Approximating the matrix exponential ...................128
4.8.1 Test results ..............................129
4.9 Conclusions and outlook...........................131
5 Conclusions 133
Appendices 135
A Algorithms 137
B Additional experiments 141
References 145
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Palavra-chave | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Centrality and Communicability Measures in Complex Networks: Analysis and Algorithms () | 2018-08-28 14:04:39 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
Kymko_thesis_Jan5.zip () | 2018-08-28 14:04:59 -0400 |
|