UNIVERSITY OF OXFORD

UNIVERSITY OF OXFORD

Centrality measures in multilayer networks

MMath BE Extended Essay

Candidate Number 303269

Hilary 2015

Abstract

Network science is an interdisciplinary academic field that has applications in many disciplines including sociology, biology, economics, operations research, and computer science. `Multilayer' networks allow multiple types of relationships to be represented in modelling. Recently, there have been some efforts to generalise `centrality' measures--indicators that quantify the importance of nodes in a network--in order that they are also applicable in multilayer networks.

In this report, we put forward a proposition that enables existing tools for centrality measures defined by random walks in undirected multilayer networks with edge weights to be directly applicable to undirected multilayer networks with both nonnegative edge weights and nonnegative node weights. We then give detailed derivations and proofs for two approaches to calculating random-walk occupation centrality, PageRank centrality, random-walk betweenness centrality and random-walk closeness centrality in multilayer networks with edge weights. One approach exploits the multilayer structure and the other generalises centrality measures directly from monoplex (i.e. single-layer) networks. We compare the two methods by ranking economies in the international trade system and through general numerical simulations.

Acknowledgements

Firstly, I would like to thank my supervisors for their consistent encouragement and advice from the very beginning of the project, which has strengthened my interest in network science. I am grateful to Dr Mikko Kivela? for creating and developing Multilayer Networks Library for Python, and Dr John D. Hunter and other contributors to the matplotlib library for Python. I also thank Dr Robert C. Feenstra and other contributors to the documentation, `World Trade Flows: 1962?2000', as well as the World Bank for publishing data for gross domestic product per capita in year 2000.

Contents

1 Introduction

6

2 Preliminary information

9

2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Tensor representations . . . . . . . . . . . . . . . . . . . . . . 9

2.1.2 Supra-adjacency representations . . . . . . . . . . . . . . . . . 12

2.2 Random walks in multilayer networks . . . . . . . . . . . . . . . . . . 13

2.2.1 Multilayer networks with edge weights . . . . . . . . . . . . . 13

2.2.2 Multilayer networks with node weights . . . . . . . . . . . . . 14

2.2.3 Multilayer networks with both edge weights and node weights 14

3 Centralities in weighted multilayer networks

16

3.1 Random-walk occupation centrality . . . . . . . . . . . . . . . . . . . 17

3.2 PageRank centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 Random-walk betweenness centrality . . . . . . . . . . . . . . . . . . 19

3.4 Random-walk closeness centrality . . . . . . . . . . . . . . . . . . . . 20

3.5 A direct generalisation from monoplex networks . . . . . . . . . . . . 20

4 Ranking economies in international trade

22

4.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2 Ranking results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5 Simulations

27

5.1 Random-graph ensembles . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2 Analysis of ranking results . . . . . . . . . . . . . . . . . . . . . . . . 28

5.2.1 Unweighted multiplex networks . . . . . . . . . . . . . . . . . 28

5.2.2 Multiplex networks with edge weights . . . . . . . . . . . . . . 30

5.2.3 Multiplex networks with node weights . . . . . . . . . . . . . 32

5.2.4 Multiplex networks with both edge weights and node weights . 34

6 Conclusions

37

Appendices

39

Bibliography

47

2

List of Figures

1.1 Schematic of a random walk (the red dotted path) in a multilayer network. At each step, a random walker can either follow an intra-layer edge (a solid line) or an inter-layer edge (a grey dashed line). The multilayer structure allows a random walker to move between nodes that are adjacent in one layer but not in another. The figure is inspired by [11]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 An example of the most general type of multilayer network. Intra-layer edges are represented by solid lines, and inter-layer edges by dashed lines. Note that any pair of node-layer tuples can be connected by an intra-layer edge if they exist on the same layer or by an inter-layer edge if they exist on different layers. The figure is inspired by [24]. . . . . . 10

2.2 An example of a multiplex network. Intra-layer edges are represented by solid lines, and inter-layer edges by dashed lines. Note that interlayer edges can only possibly exist between a node and its counterpart in a different layer. The figure is inspired by [24]. . . . . . . . . . . . 10

2.3 An example of a monoplex network, which is the underlying graph of the multilayer network in Figure 2.1. Intra-layer edges are represented by solid lines, and inter-layer edges by dashed lines. The figure is inspired by [24]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 An illustration of the supra-adjacency matrix for the multilayer network in Figure 2.1, which is also the adjacency matrix for the underlying graph in Figure 2.3. The three blocks on the main diagonal of the matrix correspond to intra-layer adjacency matrices, and the offdiagonal blocks correspond to inter-layer adjacency matrices. Suppose that the multilayer network in Figure 2.1 is unweighted, then thered and green elements are 1, and the others are 0. The figure is inspired by [24]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.1 Visualisation of the international trade multiplex network (3 layers of the 10 layers) using the Multilayer Networks Library [23]. For the sake of readability, we omit intra-layer edges with weights lower than 100000 as well as inter-layer edges. Each cyan plate is a layer, and black dots represent nodes. Lines represent intra-layer edges, with darker colour indicating larger edge weight. The figure exhibits the heterogeneity of the network in each layer: the top layer has fewer edges with larger weights than the other two layers, and nodes can have very different node strengths in different layers. . . . . . . . . . . . . . . . . . . . . 24

3

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download