TY - GEN
T1 - Network alignment by discrete Ollivier-Ricci flow
AU - Ni, Chien Chun
AU - Lin, Yu Yao
AU - Gao, Jie
AU - Gu, Xianfeng
N1 - Funding Information:
Acknowledgement. The authors would like to thanks the funding agencies NSF DMS-1737812, CNS-1618391, CCF-1535900, DMS-1418255, and AFOSR FA9550-14-1-0193.
Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - 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: https://github.com/saibalmars/GraphRicciCurvature).
AB - 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: https://github.com/saibalmars/GraphRicciCurvature).
UR - http://www.scopus.com/inward/record.url?scp=85059098878&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059098878&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-04414-5_32
DO - 10.1007/978-3-030-04414-5_32
M3 - Conference contribution
AN - SCOPUS:85059098878
SN - 9783030044138
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 447
EP - 462
BT - Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings
A2 - Biedl, Therese
A2 - Kerren, Andreas
PB - Springer Verlag
T2 - 26th International Symposium on Graph Drawing and Network Visualization, GD 2018
Y2 - 26 September 2018 through 28 September 2018
ER -