TY - GEN
T1 - Differential Equivalence Yields Network Centrality
AU - Tognazzi, Stefano
AU - Tribastone, Mirco
AU - Tschaikowski, Max
AU - Vandin, Andrea
PY - 2018
Y1 - 2018
N2 - One of the most distinctive features of collective adaptive systems (CAS) is the presence of many individuals which interact with each other and with the environment, giving rise to a system-level behaviour that cannot be analyzed by studying the single agents in isolation. The interaction structure among the individuals of CAS is often captured by networks where nodes denote individuals and edges interactions. Understanding the interplay between the network topology and the CAS dynamics calls for tools from network theory in order, for instance, to identify the most important nodes of a network. Centrality measures address this task by assigning an importance measure to each node, a possible example being the famous PageRank algorithm of Google. In this paper we investigate the relationship between centrality measures and model reduction techniques, such as lumpability of Markov chains, which seek to reduce a model into a smaller one that can be processed more efficiently, while preserving information of interest. In particular, we focus on the relation between network centrality and backward differential equivalence, a generalization of lumpability to general dynamical systems. We show that any two backward differential equivalent nodes enjoy identical centrality measures. By efficiently obtaining substantial reductions of real-world networks from biochemistry, social sciences and computer engineering, we demonstrate the applicability of the result.
AB - One of the most distinctive features of collective adaptive systems (CAS) is the presence of many individuals which interact with each other and with the environment, giving rise to a system-level behaviour that cannot be analyzed by studying the single agents in isolation. The interaction structure among the individuals of CAS is often captured by networks where nodes denote individuals and edges interactions. Understanding the interplay between the network topology and the CAS dynamics calls for tools from network theory in order, for instance, to identify the most important nodes of a network. Centrality measures address this task by assigning an importance measure to each node, a possible example being the famous PageRank algorithm of Google. In this paper we investigate the relationship between centrality measures and model reduction techniques, such as lumpability of Markov chains, which seek to reduce a model into a smaller one that can be processed more efficiently, while preserving information of interest. In particular, we focus on the relation between network centrality and backward differential equivalence, a generalization of lumpability to general dynamical systems. We show that any two backward differential equivalent nodes enjoy identical centrality measures. By efficiently obtaining substantial reductions of real-world networks from biochemistry, social sciences and computer engineering, we demonstrate the applicability of the result.
KW - Networks
KW - Centrality measures
KW - Model reduction
KW - Efficient algorithms
U2 - 10.1007/978-3-030-03424-5_13
DO - 10.1007/978-3-030-03424-5_13
M3 - Article in proceedings
SN - 9783030034238
VL - 11246
T3 - Lecture Notes in Computer Science
SP - 186
EP - 201
BT - Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems
PB - Springer
T2 - International Symposium on Leveraging Applications of Formal Methods
Y2 - 5 November 2018 through 9 November 2018
ER -