Matching Graphs with Community Structure

A Concentration of Measure Approach

Farhad Shirani, Siddharth Garg, Elza Erkip

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

Abstract

In this paper, matching pairs of random graphs under the community structure model is considered. The problem emerges naturally in various applications such as privacy, image processing and DNA sequencing. A pair of randomly generated labeled graphs with pairwise correlated edges are considered. It is assumed that the graph edges are generated based on the community structure model. Given the labeling of the edges of the first graph, the objective is to recover the labels in the second graph. The problem is considered under two scenarios: i) with side-information where the community membership of the nodes in both graphs are known, and ii) without side-information where the community memberships are not known. A matching scheme is proposed which operates based on typicality of the adjacency matrices of the graphs. Achievability results are derived which provide theoretical guarantees for successful matching under specific assumptions on graph parameters. It is observed that for the proposed matching scheme, the conditions for successful matching do not change in the presence of side-information. Furthermore, a converse result is derived which characterizes a set of graph parameters for which matching is not possible.

Original languageEnglish (US)
Title of host publication2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1028-1035
Number of pages8
ISBN (Electronic)9781538665961
DOIs
StatePublished - Feb 5 2019
Event56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 - Monticello, United States
Duration: Oct 2 2018Oct 5 2018

Publication series

Name2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

Conference

Conference56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
CountryUnited States
CityMonticello
Period10/2/1810/5/18

Fingerprint

Concentration of Measure
Graph Matching
Community Structure
Model structures
Graph in graph theory
Labeling
Side Information
Labels
Image processing
DNA
DNA Sequencing
Adjacency Matrix
Random Graphs
Converse
Privacy
Pairwise
Image Processing
Scenarios

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Cite this

Shirani, F., Garg, S., & Erkip, E. (2019). Matching Graphs with Community Structure: A Concentration of Measure Approach. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 (pp. 1028-1035). [8636015] (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2018.8636015

Matching Graphs with Community Structure : A Concentration of Measure Approach. / Shirani, Farhad; Garg, Siddharth; Erkip, Elza.

2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1028-1035 8636015 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).

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

Shirani, F, Garg, S & Erkip, E 2019, Matching Graphs with Community Structure: A Concentration of Measure Approach. in 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018., 8636015, 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Institute of Electrical and Electronics Engineers Inc., pp. 1028-1035, 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Monticello, United States, 10/2/18. https://doi.org/10.1109/ALLERTON.2018.8636015
Shirani F, Garg S, Erkip E. Matching Graphs with Community Structure: A Concentration of Measure Approach. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 1028-1035. 8636015. (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). https://doi.org/10.1109/ALLERTON.2018.8636015
Shirani, Farhad ; Garg, Siddharth ; Erkip, Elza. / Matching Graphs with Community Structure : A Concentration of Measure Approach. 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 1028-1035 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).
@inproceedings{743a861e5fed4b51997dd78b3e042ddf,
title = "Matching Graphs with Community Structure: A Concentration of Measure Approach",
abstract = "In this paper, matching pairs of random graphs under the community structure model is considered. The problem emerges naturally in various applications such as privacy, image processing and DNA sequencing. A pair of randomly generated labeled graphs with pairwise correlated edges are considered. It is assumed that the graph edges are generated based on the community structure model. Given the labeling of the edges of the first graph, the objective is to recover the labels in the second graph. The problem is considered under two scenarios: i) with side-information where the community membership of the nodes in both graphs are known, and ii) without side-information where the community memberships are not known. A matching scheme is proposed which operates based on typicality of the adjacency matrices of the graphs. Achievability results are derived which provide theoretical guarantees for successful matching under specific assumptions on graph parameters. It is observed that for the proposed matching scheme, the conditions for successful matching do not change in the presence of side-information. Furthermore, a converse result is derived which characterizes a set of graph parameters for which matching is not possible.",
author = "Farhad Shirani and Siddharth Garg and Elza Erkip",
year = "2019",
month = "2",
day = "5",
doi = "10.1109/ALLERTON.2018.8636015",
language = "English (US)",
series = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1028--1035",
booktitle = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",

}

TY - GEN

T1 - Matching Graphs with Community Structure

T2 - A Concentration of Measure Approach

AU - Shirani, Farhad

AU - Garg, Siddharth

AU - Erkip, Elza

PY - 2019/2/5

Y1 - 2019/2/5

N2 - In this paper, matching pairs of random graphs under the community structure model is considered. The problem emerges naturally in various applications such as privacy, image processing and DNA sequencing. A pair of randomly generated labeled graphs with pairwise correlated edges are considered. It is assumed that the graph edges are generated based on the community structure model. Given the labeling of the edges of the first graph, the objective is to recover the labels in the second graph. The problem is considered under two scenarios: i) with side-information where the community membership of the nodes in both graphs are known, and ii) without side-information where the community memberships are not known. A matching scheme is proposed which operates based on typicality of the adjacency matrices of the graphs. Achievability results are derived which provide theoretical guarantees for successful matching under specific assumptions on graph parameters. It is observed that for the proposed matching scheme, the conditions for successful matching do not change in the presence of side-information. Furthermore, a converse result is derived which characterizes a set of graph parameters for which matching is not possible.

AB - In this paper, matching pairs of random graphs under the community structure model is considered. The problem emerges naturally in various applications such as privacy, image processing and DNA sequencing. A pair of randomly generated labeled graphs with pairwise correlated edges are considered. It is assumed that the graph edges are generated based on the community structure model. Given the labeling of the edges of the first graph, the objective is to recover the labels in the second graph. The problem is considered under two scenarios: i) with side-information where the community membership of the nodes in both graphs are known, and ii) without side-information where the community memberships are not known. A matching scheme is proposed which operates based on typicality of the adjacency matrices of the graphs. Achievability results are derived which provide theoretical guarantees for successful matching under specific assumptions on graph parameters. It is observed that for the proposed matching scheme, the conditions for successful matching do not change in the presence of side-information. Furthermore, a converse result is derived which characterizes a set of graph parameters for which matching is not possible.

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

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

U2 - 10.1109/ALLERTON.2018.8636015

DO - 10.1109/ALLERTON.2018.8636015

M3 - Conference contribution

T3 - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

SP - 1028

EP - 1035

BT - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -