Evolving networks

Eras and turning points

Michele Berlingerio, Michele Coscia, Fosca Giannotti, Anna Monreale, Dino Pedreschi

Research output: Contribution to journalArticle

Abstract

Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.

Original languageEnglish
Pages (from-to)27-48
Number of pages22
JournalIntelligent Data Analysis
Volume17
Issue number1
DOIs
Publication statusPublished - 2013
Externally publishedYes

Fingerprint

Turning Point
Complex networks
Electric network analysis
Labeling
Semantics
Snapshot
Dissimilarity Measure
Complex Analysis
Hierarchical Clustering
Network Analysis
Graph in graph theory
Bottom-up
Complex Networks
Null
Attack
Clustering
Entire
Moment
Methodology
Coefficient

Keywords

  • Evolution of networks
  • semantic dimension
  • turning points

Cite this

Berlingerio, M., Coscia, M., Giannotti, F., Monreale, A., & Pedreschi, D. (2013). Evolving networks: Eras and turning points. Intelligent Data Analysis, 17(1), 27-48. https://doi.org/10.3233/IDA-120566
Berlingerio, Michele ; Coscia, Michele ; Giannotti, Fosca ; Monreale, Anna ; Pedreschi, Dino. / Evolving networks : Eras and turning points. In: Intelligent Data Analysis. 2013 ; Vol. 17, No. 1. pp. 27-48.
@article{c7f963c04252478faae883fb14e6fceb,
title = "Evolving networks: Eras and turning points",
abstract = "Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.",
keywords = "Evolution of networks, semantic dimension, turning points",
author = "Michele Berlingerio and Michele Coscia and Fosca Giannotti and Anna Monreale and Dino Pedreschi",
year = "2013",
doi = "10.3233/IDA-120566",
language = "English",
volume = "17",
pages = "27--48",
journal = "Intelligent Data Analysis",
issn = "1088-467X",
publisher = "IOS Press",
number = "1",

}

Berlingerio, M, Coscia, M, Giannotti, F, Monreale, A & Pedreschi, D 2013, 'Evolving networks: Eras and turning points', Intelligent Data Analysis, vol. 17, no. 1, pp. 27-48. https://doi.org/10.3233/IDA-120566

Evolving networks : Eras and turning points. / Berlingerio, Michele; Coscia, Michele; Giannotti, Fosca; Monreale, Anna; Pedreschi, Dino.

In: Intelligent Data Analysis, Vol. 17, No. 1, 2013, p. 27-48.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Evolving networks

T2 - Eras and turning points

AU - Berlingerio, Michele

AU - Coscia, Michele

AU - Giannotti, Fosca

AU - Monreale, Anna

AU - Pedreschi, Dino

PY - 2013

Y1 - 2013

N2 - Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.

AB - Within the large body of research in complex network analysis, an important topic is the temporal evolution of networks. Existing approaches aim at analyzing the evolution on the global and the local scale, extracting properties of either the entire network or local patterns. In this paper, we focus on detecting clusters of temporal snapshots of a network, to be interpreted as eras of evolution. To this aim, we introduce a novel hierarchical clustering methodology, based on a dissimilarity measure (derived from the Jaccard coefficient) between two temporal snapshots of the network, able to detect the turning points at the beginning of the eras. We devise a framework to discover and browse the eras, either in top-down or a bottom-up fashion, supporting the exploration of the evolution at any level of temporal resolution. We show how our approach applies to real networks and null models, by detecting eras in an evolving co-authorship graph extracted from a bibliographic dataset, a collaboration graph extracted from a cinema database, and a network extracted from a database of terrorist attacks; we illustrate how the discovered temporal clustering highlights the crucial moments when the networks witnessed profound changes in their structure. Our approach is finally boosted by introducing a meaningful labeling of the obtained clusters, such as the characterizing topics of each discovered era, thus adding a semantic dimension to our analysis.

KW - Evolution of networks

KW - semantic dimension

KW - turning points

UR - http://www.scopus.com/inward/record.url?scp=84874387093&partnerID=8YFLogxK

U2 - 10.3233/IDA-120566

DO - 10.3233/IDA-120566

M3 - Article

VL - 17

SP - 27

EP - 48

JO - Intelligent Data Analysis

JF - Intelligent Data Analysis

SN - 1088-467X

IS - 1

ER -

Berlingerio M, Coscia M, Giannotti F, Monreale A, Pedreschi D. Evolving networks: Eras and turning points. Intelligent Data Analysis. 2013;17(1):27-48. https://doi.org/10.3233/IDA-120566