Network alignment by discrete Ollivier-Ricci flow

Chien Chun Ni, Yu Yao Lin, Jie Gao, Xianfeng Gu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


In this paper, we consider the problem of approximately aligning/matching two graphs. Given two graphs G1 = (V1, E1) and G2 = (V2, E2), the objective is to map nodes u, v ∈ G1 to nodes u',v' ∈ G2 such that when u, v have an edge in G1, very likely their corresponding nodes u',v' in G2 are connected as well. This problem with subgraph isomorphism as a special case has extra challenges when we consider matching complex networks exhibiting the small world phenomena. In this work, we propose to use ‘Ricci flow metric’, to define the distance between two nodes in a network. This is then used to define similarity of a pair of nodes in two networks respectively, which is the crucial step of network alignment. Specifically, the Ricci curvature of an edge describes intuitively how well the local neighborhood is connected. The graph Ricci flow uniformizes discrete Ricci curvature and induces a Ricci flow metric that is insensitive to node/edge insertions and deletions. With the new metric, we can map a node in G1 to a node in G2 whose distance vector to only a few preselected landmarks is the most similar. The robustness of the graph metric makes it outperform other methods when tested on various complex graph models and real world network data sets (Emails, Internet, and protein interaction networks) (The source code of computing Ricci curvature and Ricci flow metric are available:

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings
EditorsTherese Biedl, Andreas Kerren
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783030044138
StatePublished - 2018
Externally publishedYes
Event26th International Symposium on Graph Drawing and Network Visualization, GD 2018 - Barcelona, Spain
Duration: Sep 26 2018Sep 28 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11282 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th International Symposium on Graph Drawing and Network Visualization, GD 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Network alignment by discrete Ollivier-Ricci flow'. Together they form a unique fingerprint.

Cite this