EIGENVECTOR-BASED CENTRALITY MEASURES FOR TEMPORAL NETWORKS.

Published on Mar 28, 2017in Multiscale Modeling & Simulation1.855
· DOI :10.1137/16M1066142
Dane Taylor17
Estimated H-index: 17
(Statistical and Applied Mathematical Sciences Institute),
Sean A. Myers3
Estimated H-index: 3
(UNC: University of North Carolina at Chapel Hill)
+ 2 AuthorsPeter J. Mucha51
Estimated H-index: 51
(UNC: University of North Carolina at Chapel Hill)
Sources
Abstract
Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with Nnodes as a sequence of Tlayers that describe the network during different time windows, and we couple centrality matrices for the layers into a supracentrality matrix of size NT\times NTwhose dominant eigenvector gives the centrality of each node iat each time t We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node iand the time layer t We also introduce the concepts of marginal and conditional...
📖 Papers frequently viewed together
1,381 Citations
1,497 Citations
9 Authors (Wang Zhen)
2,073 Citations
References57
Newest
#1Keyou You (THU: Tsinghua University)H-Index: 24
#2Roberto Tempo (Polytechnic University of Turin)H-Index: 52
Last. Li Qiu (HKUST: Hong Kong University of Science and Technology)H-Index: 33
view all 3 authors...
This paper is concerned with distributed computation of several commonly used centrality measures in complex networks. In particular, we propose deterministic algorithms, which converge in finite time, for the distributed computation of the degree, closeness and betweenness centrality measures in directed graphs. Regarding eigenvector centrality, we consider the PageRank problem as its typical variant, and design distributed randomized algorithms to compute PageRank for both fixed and time-varyi...
53 CitationsSource
#1Floriana Gargiulo (Université de Namur)H-Index: 16
#2Auguste Caen (IRIA: French Institute for Research in Computer Science and Automation)H-Index: 1
Last. Timoteo Carletti (Université de Namur)H-Index: 20
view all 4 authors...
This paper introduces a data-driven methodology to study the historical evolution of mathematical thinking and its spatial spreading. To do so, we have collected and integrated data from different online academic datasets. In its final form, the database includes a large number (\(N\sim200\mbox{K}\)) of advisor-student relationships, with affiliations and keywords on their research topic, over several centuries, from the 14th century until today. We focus on two different issues, the evolving im...
24 CitationsSource
#2Manlio De Domenico (URV: Rovira i Virgili University)H-Index: 29
Last. Alexandre Arenas (URV: Rovira i Virgili University)H-Index: 5
view all 4 authors...
Abstract Real-world complex systems exhibit multiple levels of relationships. In many cases they require to be modeled as interconnected multilayer networks, characterizing interactions of several types simultaneously. It is of crucial importance in many fields, from economics to biology and from urban planning to social sciences, to identify the most (or the less) influent nodes in a network using centrality measures. However, defining the centrality of actors in interconnected complex networks...
66 CitationsSource
#1Mason A. PorterH-Index: 68
#2James P. GleesonH-Index: 31
This volume is a tutorial for the study of dynamical systems on networks. It discusses both methodology and models, including spreading models for social and biological contagions. The authors focus especially on simple situations that are analytically tractable, because they are insightful and provide useful springboards for the study of more complicated scenarios. This tutorial, which also includes key pointers to the literature, should be helpful for junior and senior undergraduate students, ...
105 Citations
#1Matthew J. Williams (UCL: University College London)H-Index: 14
#2Mirco Musolesi (UCL: University College London)H-Index: 54
Recent advances in spatial and temporal networks have enabled researchers to more-accurately describe many real-world systems such as urban transport networks. In this paper, we study the response of real-world spatio-temporal networks to random error and systematic attack, taking a unified view of their spatial and temporal performance. We propose a model of spatio-temporal paths in time-varying spatially embedded networks which captures the property that, as in many real-world systems, interac...
53 CitationsSource
In the case of graph partitioning, the emergence of localized eigenvectors can cause the standard spectral method to fail. To overcome this problem, the spectral method using a non-backtracking matrix was proposed. Based on numerical experiments on several examples of real networks, it is clear that the non-backtracking matrix does not exhibit localization of eigenvectors. However, we show that localized eigenvectors of the non-backtracking matrix can exist outside the spectral band, which may l...
14 CitationsSource
#1Taro Takaguchi (NII: National Institute of Informatics)H-Index: 13
#2Yosuke YanoH-Index: 4
Last. Yuichi Yoshida (NII: National Institute of Informatics)H-Index: 23
view all 3 authors...
Structure of real networked systems, such as social relationship, can be modeled as temporal networks in which each edge appears only at the prescribed time. Understanding the structure of temporal networks requires quantifying the importance of a temporal vertex, which is a pair of vertex index and time. In this paper, we define two centrality measures of a temporal vertex based on the fastest temporal paths which use the temporal vertex. The definition is free from parameters and robust agains...
29 CitationsSource
#1Romualdo Pastor-Satorras (UPC: Polytechnic University of Catalonia)H-Index: 62
#2Claudio CastellanoH-Index: 61
The spectral properties of the adjacency matrix provide a trove of information about the structure and function of complex networks. In particular, the largest eigenvalue and its associated principal eigenvector are crucial in the understanding of nodes’ centrality and the unfolding of dynamical processes. Here we show that two distinct types of localization of the principal eigenvector may occur in heterogeneous networks. For synthetic networks with degree distribution P(q) ~ q−γ, localization ...
77 CitationsSource
#1Petter Holme (SKKU: Sungkyunkwan University)H-Index: 51
The power of any kind of network approach lies in the ability to simplify a complex system so that one can better understand its function as a whole. Sometimes it is beneficial, however, to include more information than in a simple graph of only nodes and links. Adding information about times of interactions can make predictions and mechanistic understanding more accurate. The drawback, however, is that there are not so many methods available, partly because temporal networks is a relatively you...
485 CitationsSource
Google's PageRank method was developed to evaluate the importance of web-pages via their link structure. The mathematics of PageRank, however, are entirely general and apply to any graph or network in any domain. Thus, PageRank is now regularly used in bibliometrics, social and information network analysis, and for link prediction and recommendation. It's even used for systems analysis of road networks, as well as biology, chemistry, neuroscience, and physics. We'll see the mathematics and ideas...
351 CitationsSource
Cited By89
Newest
#1Patrick HoscheitH-Index: 6
#2Eric Anthony (Université Paris-Saclay)H-Index: 1
Last. Elisabeta Vergu (Université Paris-Saclay)H-Index: 6
view all 3 authors...
We study network centrality measures that take into account the specific structure of networks with time-stamped edges. In particular, we explore how such measures can be used to identify nodes most relevant for the spread of epidemics on directed, temporal contact networks. We present a percolation study on the French cattle trade network, proving that time-aware centrality measures such as the TempoRank significantly outperform measures defined on the static network. In order to make TempoRank...
Source
#1Carolina Mattsson (NU: Northeastern University)H-Index: 1
#2Frank W. Takes (LEI: Leiden University)H-Index: 12
What do football passes and financial transactions have in common? Both are networked walk processes that we can observe, where records take the form of timestamped events that move something tangible from one node to another. Here we propose an approach to analyze this type of data that extracts the actual trajectories taken by the tangible items involved. The main advantage of analyzing the resulting trajectories compared to using, e.g., existing temporal network analysis techniques, is that s...
Source
#1Laishui Lv (Nanjing University of Science and Technology)H-Index: 2
#2Kun Zhang (Nanjing University of Science and Technology)H-Index: 1
Last. Wei Xue (Anhui University of Technology)H-Index: 1
view all 7 authors...
Abstract null null In recent years, many centralities have been developed to identify the key nodes in multilayer and temporal networks. Among these centrality measures, eigenvector-based centralities are very efficient ranking algorithms. In the real world, some complex systems have multilayer structure and edges are dynamic, i.e., they appear and disappear over time, referred to as the multilayer temporal networks. Moreover, some eigenvector-based centralities have been extended to rank the no...
Source
#1Jiu-lei Jiang (MUC: Minzu University of China)
#2Hui Fang (MUC: Minzu University of China)
Last. Wei-min Li (SHU: Shanghai University)
view all 4 authors...
Abstract null null The identification of important nodes in a temporal network is of great significance for the analysis and control of the information dissemination process. In this work, the multi-layer coupled network analysis method is employed to identify important nodes in a temporal network. First, to overcome the problem of a fixed constant being unable to reflect differences in the inter-layer coupling relationship, and by combining a node’s own neighbors and common neighbors of nodes i...
Source
#1Mustafa Yildirim (Gazi University)
#2Feyza Yildirim Okay (Gazi University)H-Index: 5
Last. Suat Ozdemir (Hacettepe University)H-Index: 22
view all 3 authors...
Abstract With the unprecedented increase in data all over the world, financial sector such as companies and industries try to remain competitive by transforming themselves into data-driven organizations. By analyzing a huge amount of financial data, companies are able to obtain valuable information to determine their strategic plans such as risk control, crisis management, or growth management. However, as the amount of data increase dramatically, traditional data analytic platforms confront wit...
4 CitationsSource
#1Bahareh Najafi (U of T: University of Toronto)
#2Saeedeh Parsaeefard (U of T: University of Toronto)H-Index: 15
Last. Alberto Leon-Garcia (U of T: University of Toronto)H-Index: 34
view all 3 authors...
GNNs have been proven to perform highly effective in various node-level, edge-level, and graph-level prediction tasks in several domains. Existing approaches mainly focus on static graphs. However, many graphs change over time with their edge may disappear, or node or edge attribute may alter from one time to the other. It is essential to consider such evolution in representation learning of nodes in time varying graphs. In this paper, we propose a Temporal Multilayered Position-aware Graph Neur...
#1Marcin WaniekH-Index: 7
#2Petter HolmeH-Index: 51
Last. Talal RahwanH-Index: 25
view all 3 authors...
Social network analysis tools can infer various attributes just by scrutinizing one's connections. Several researchers have studied the problem faced by an evader whose goal is to strategically rewire their social connections in order to mislead such tools, thereby concealing their private attributes. However, to date, this literature has only considered static networks, while neglecting the more general case of temporal networks, where the structure evolves over time. Driven by this observation...
We study urban public transport systems by means of multiplex networks in which stops are represented as nodes and each line is represented by a layer. We determine and visualize public transport network orientations and compare them with street network orientations of the 36largest German as well as 18selected major European cities. We find that German urban public transport networks are mainly oriented in a direction close to the cardinal east-west axis, which usually coincides with one ...
In this short tutorial, we cover recent methods to analyze and model network data accessible as a stream of edges, such as interactions in a social network service, or any other graph database with real-time updates from a stream. First we introduce the data streaming computational model and give examples of the so-called temporal networks. We describe how traditional graph properties (sampling, subgraph counting, graph query evaluation, etc.), low-rank approximation, network embedding, link pre...
Source
#1Marina H. L. Duarte (PUC-MG: Pontifícia Universidade Católica de Minas Gerais)H-Index: 7
#2Diego Llusia (UAM: Autonomous University of Madrid)H-Index: 12
Last. Luciana B. Nascimento (PUC-MG: Pontifícia Universidade Católica de Minas Gerais)H-Index: 9
view all 4 authors...
Source