Differential Equivalence Yields Network Centrality

Stefano Tognazzi, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationLeveraging Applications of Formal Methods, Verification and Validation. Distributed Systems
Volume11246
PublisherSpringer
Publication date2018
Pages186-201
ISBN (Print)9783030034238
DOIs
Publication statusPublished - 2018
EventInternational Symposium on Leveraging Applications of Formal Methods - Limassol, Cyprus
Duration: 5 Nov 20189 Nov 2018

Conference

ConferenceInternational Symposium on Leveraging Applications of Formal Methods
CountryCyprus
CityLimassol
Period05/11/201809/11/2018
SeriesLecture Notes in Computer Science
Volume11246
ISSN0302-9743

Keywords

  • Networks
  • Centrality measures
  • Model reduction
  • Efficient algorithms

Cite this

Tognazzi, S., Tribastone, M., Tschaikowski, M., & Vandin, A. (2018). Differential Equivalence Yields Network Centrality. In Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems (Vol. 11246, pp. 186-201). Springer. Lecture Notes in Computer Science, Vol.. 11246 https://doi.org/10.1007/978-3-030-03424-5_13
Tognazzi, Stefano ; Tribastone, Mirco ; Tschaikowski, Max ; Vandin, Andrea. / Differential Equivalence Yields Network Centrality. Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems. Vol. 11246 Springer, 2018. pp. 186-201 (Lecture Notes in Computer Science, Vol. 11246).
@inproceedings{d79aae4303c74ce9a8671d01c4f8e7c6,
title = "Differential Equivalence Yields Network Centrality",
abstract = "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.",
keywords = "Networks, Centrality measures, Model reduction, Efficient algorithms",
author = "Stefano Tognazzi and Mirco Tribastone and Max Tschaikowski and Andrea Vandin",
year = "2018",
doi = "10.1007/978-3-030-03424-5_13",
language = "English",
isbn = "9783030034238",
volume = "11246",
pages = "186--201",
booktitle = "Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems",
publisher = "Springer",

}

Tognazzi, S, Tribastone, M, Tschaikowski, M & Vandin, A 2018, Differential Equivalence Yields Network Centrality. in Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems. vol. 11246, Springer, Lecture Notes in Computer Science, vol. 11246, pp. 186-201, International Symposium on Leveraging Applications of Formal Methods, Limassol, Cyprus, 05/11/2018. https://doi.org/10.1007/978-3-030-03424-5_13

Differential Equivalence Yields Network Centrality. / Tognazzi, Stefano; Tribastone, Mirco; Tschaikowski, Max; Vandin, Andrea.

Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems. Vol. 11246 Springer, 2018. p. 186-201 (Lecture Notes in Computer Science, Vol. 11246).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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

SP - 186

EP - 201

BT - Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems

PB - Springer

ER -

Tognazzi S, Tribastone M, Tschaikowski M, Vandin A. Differential Equivalence Yields Network Centrality. In Leveraging Applications of Formal Methods, Verification and Validation. Distributed Systems. Vol. 11246. Springer. 2018. p. 186-201. (Lecture Notes in Computer Science, Vol. 11246). https://doi.org/10.1007/978-3-030-03424-5_13