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
Country/TerritoryCyprus
CityLimassol
Period05/11/201809/11/2018
SeriesLecture Notes in Computer Science
Volume11246
ISSN0302-9743

Keywords

  • Networks
  • Centrality measures
  • Model reduction
  • Efficient algorithms

Fingerprint

Dive into the research topics of 'Differential Equivalence Yields Network Centrality'. Together they form a unique fingerprint.

Cite this