PDGM: Percolation-based directed graph matching in social networks

Lijing Wang, Jin Hee Cho, Ing Ray Chen, Jiangzhuo Chen

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

2 Scopus citations


Linking multiple accounts owned by the same user across different online social networks (OSNs) is an important issue in social networks, known as identity reconciliation. Graph matching is one of popular techniques to solve this problem by identifying a map that matches a set of vertices across different OSNs. Among them, percolation-based graph matching (PGM) has been explored to identify entities belonging to a same user across two different networks based on a set of initial pre-matched seed nodes and graph structural information. However, existing PGM algorithms have been applied in only undirected networks while many OSNs are represented by directional relationships (e.g., followers or followees in Twitter or Facebook). For PGM to be applicable in real world OSNs represented by directed networks with a small set of overlapping vertices, we propose a percolation-based directed graph matching algorithm, namely PDGM, by considering the following two key features: (1) similarity of two nodes based on directional relationships (i.e., outgoing edges vs. incoming edges); and (2) celebrity penalty such as penalty given for nodes with a high in-degree. Through the extensive simulation experiments, our results show that the proposed PDGM outperforms the baseline PGM counterpart that does not consider either directional relationships or celebrity penalty.

Original languageEnglish (US)
Title of host publication2017 IEEE International Conference on Communications, ICC 2017
EditorsMerouane Debbah, David Gesbert, Abdelhamid Mellouk
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467389990
StatePublished - Jul 28 2017
Externally publishedYes
Event2017 IEEE International Conference on Communications, ICC 2017 - Paris, France
Duration: May 21 2017May 25 2017

Publication series

NameIEEE International Conference on Communications
ISSN (Print)1550-3607


Other2017 IEEE International Conference on Communications, ICC 2017

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'PDGM: Percolation-based directed graph matching in social networks'. Together they form a unique fingerprint.

Cite this