Mining connection pathways for marked nodes in large graphs

Leman Akoglu; Jilles Vreeken; Hanghang Tong; Duen Horng Chau; Nikolaj Tatti; Christos Faloutsos

doi:10.1137/1.9781611972832.5

Mining connection pathways for marked nodes in large graphs

Leman Akoglu, Jilles Vreeken, Hanghang Tong, Duen Horng Chau, Nikolaj Tatti, Christos Faloutsos

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these nodes? Are they close together in the graph? or, if segregated, how many groups do they form? We approach this problem by trying to find sets of simple connection pathways between sets of marked nodes. We formalize the problem in terms of the Minimum Description Length principle: a pathway is simple when we need only few bits to tell which edges to follow, such that we visit all nodes in a group. Then, the best partitioning is the one that requires the least number of bits to describe the paths that visit all the marked nodes. We prove that solving this problem is NP-hard, and introduce DOT2DOT, an efficient algorithm for partitioning marked nodes by finding simple pathways between nodes. Experimentation shows that DOT2DOT correctly groups nodes for which good connection paths can be constructed, while separating distant nodes.

Original language	English (US)
Title of host publication	Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
Editors	Joydeep Ghosh, Zoran Obradovic, Jennifer Dy, Zhi-Hua Zhou, Chandrika Kamath, Srinivasan Parthasarathy
Publisher	Siam Society under Royal Patronage
Pages	37-45
Number of pages	9
ISBN (Electronic)	9781611972627
DOIs	https://doi.org/10.1137/1.9781611972832.5
State	Published - 2013
Externally published	Yes
Event	SIAM International Conference on Data Mining, SDM 2013 - Austin, United States Duration: May 2 2013 → May 4 2013

Publication series

Name	Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013

Other

Other	SIAM International Conference on Data Mining, SDM 2013
Country/Territory	United States
City	Austin
Period	5/2/13 → 5/4/13

ASJC Scopus subject areas

Computer Science Applications
Software
Theoretical Computer Science
Information Systems
Signal Processing

Online availability

10.1137/1.9781611972832.5

Library availability

Discover UIUC Full Text

Cite this

Akoglu, L., Vreeken, J., Tong, H., Chau, D. H., Tatti, N., & Faloutsos, C. (2013). Mining connection pathways for marked nodes in large graphs. In J. Ghosh, Z. Obradovic, J. Dy, Z.-H. Zhou, C. Kamath, & S. Parthasarathy (Eds.), Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013 (pp. 37-45). (Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013). Siam Society under Royal Patronage. https://doi.org/10.1137/1.9781611972832.5

Mining connection pathways for marked nodes in large graphs. / Akoglu, Leman; Vreeken, Jilles; Tong, Hanghang et al.
Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013. ed. / Joydeep Ghosh; Zoran Obradovic; Jennifer Dy; Zhi-Hua Zhou; Chandrika Kamath; Srinivasan Parthasarathy. Siam Society under Royal Patronage, 2013. p. 37-45 (Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Akoglu, L, Vreeken, J, Tong, H, Chau, DH, Tatti, N & Faloutsos, C 2013, Mining connection pathways for marked nodes in large graphs. in J Ghosh, Z Obradovic, J Dy, Z-H Zhou, C Kamath & S Parthasarathy (eds), Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013. Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013, Siam Society under Royal Patronage, pp. 37-45, SIAM International Conference on Data Mining, SDM 2013, Austin, United States, 5/2/13. https://doi.org/10.1137/1.9781611972832.5

Akoglu L, Vreeken J, Tong H, Chau DH, Tatti N, Faloutsos C. Mining connection pathways for marked nodes in large graphs. In Ghosh J, Obradovic Z, Dy J, Zhou ZH, Kamath C, Parthasarathy S, editors, Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013. Siam Society under Royal Patronage. 2013. p. 37-45. (Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013). doi: 10.1137/1.9781611972832.5

Akoglu, Leman ; Vreeken, Jilles ; Tong, Hanghang et al. / Mining connection pathways for marked nodes in large graphs. Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013. editor / Joydeep Ghosh ; Zoran Obradovic ; Jennifer Dy ; Zhi-Hua Zhou ; Chandrika Kamath ; Srinivasan Parthasarathy. Siam Society under Royal Patronage, 2013. pp. 37-45 (Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013).

@inproceedings{03586e0888254a1d8fa2f4a350b45820,

title = "Mining connection pathways for marked nodes in large graphs",

abstract = "Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these nodes? Are they close together in the graph? or, if segregated, how many groups do they form? We approach this problem by trying to find sets of simple connection pathways between sets of marked nodes. We formalize the problem in terms of the Minimum Description Length principle: a pathway is simple when we need only few bits to tell which edges to follow, such that we visit all nodes in a group. Then, the best partitioning is the one that requires the least number of bits to describe the paths that visit all the marked nodes. We prove that solving this problem is NP-hard, and introduce DOT2DOT, an efficient algorithm for partitioning marked nodes by finding simple pathways between nodes. Experimentation shows that DOT2DOT correctly groups nodes for which good connection paths can be constructed, while separating distant nodes.",

author = "Leman Akoglu and Jilles Vreeken and Hanghang Tong and Chau, {Duen Horng} and Nikolaj Tatti and Christos Faloutsos",

note = "Publisher Copyright: Copyright {\textcopyright} SIAM.; SIAM International Conference on Data Mining, SDM 2013 ; Conference date: 02-05-2013 Through 04-05-2013",

year = "2013",

doi = "10.1137/1.9781611972832.5",

language = "English (US)",

series = "Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013",

publisher = "Siam Society under Royal Patronage",

pages = "37--45",

editor = "Joydeep Ghosh and Zoran Obradovic and Jennifer Dy and Zhi-Hua Zhou and Chandrika Kamath and Srinivasan Parthasarathy",

booktitle = "Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013",

}

TY - GEN

T1 - Mining connection pathways for marked nodes in large graphs

AU - Akoglu, Leman

AU - Vreeken, Jilles

AU - Tong, Hanghang

AU - Chau, Duen Horng

AU - Tatti, Nikolaj

AU - Faloutsos, Christos

PY - 2013

Y1 - 2013

N2 - Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these nodes? Are they close together in the graph? or, if segregated, how many groups do they form? We approach this problem by trying to find sets of simple connection pathways between sets of marked nodes. We formalize the problem in terms of the Minimum Description Length principle: a pathway is simple when we need only few bits to tell which edges to follow, such that we visit all nodes in a group. Then, the best partitioning is the one that requires the least number of bits to describe the paths that visit all the marked nodes. We prove that solving this problem is NP-hard, and introduce DOT2DOT, an efficient algorithm for partitioning marked nodes by finding simple pathways between nodes. Experimentation shows that DOT2DOT correctly groups nodes for which good connection paths can be constructed, while separating distant nodes.

AB - Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these nodes? Are they close together in the graph? or, if segregated, how many groups do they form? We approach this problem by trying to find sets of simple connection pathways between sets of marked nodes. We formalize the problem in terms of the Minimum Description Length principle: a pathway is simple when we need only few bits to tell which edges to follow, such that we visit all nodes in a group. Then, the best partitioning is the one that requires the least number of bits to describe the paths that visit all the marked nodes. We prove that solving this problem is NP-hard, and introduce DOT2DOT, an efficient algorithm for partitioning marked nodes by finding simple pathways between nodes. Experimentation shows that DOT2DOT correctly groups nodes for which good connection paths can be constructed, while separating distant nodes.

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

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

U2 - 10.1137/1.9781611972832.5

DO - 10.1137/1.9781611972832.5

M3 - Conference contribution

AN - SCOPUS:84960112617

T3 - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013

SP - 37

EP - 45

BT - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013

A2 - Ghosh, Joydeep

A2 - Obradovic, Zoran

A2 - Dy, Jennifer

A2 - Zhou, Zhi-Hua

A2 - Kamath, Chandrika

A2 - Parthasarathy, Srinivasan

PB - Siam Society under Royal Patronage

T2 - SIAM International Conference on Data Mining, SDM 2013

Y2 - 2 May 2013 through 4 May 2013

ER -

Mining connection pathways for marked nodes in large graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this