Project
back
Connection Pathways in Large Graphs
with Leman Akoglu, Hanghang Tong, Polo Chau, Nikolaj Tatti & Christos Faloutsos

Abstract. Suppose we are given a large graph in which, by an 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.

Implementation

the MatLab source code (October 2012) by Leman Akoglu.

Related Publications
Akoglu, L, Vreeken, J, Tong, H, Chau, DH, Tatti, N & Faloutsos, C Mining Connection Pathways for Marked Nodes in Large Graphs. In: Proceedings of the SIAM International Conference on Data Mining (SDM), pp 37-45, SIAM, 2013. (oral presentation, 14.4% acceptance rate; overal 25%)
Akoglu, L, Vreeken, J, Tong, H, Chau, DH, Tatti, N & Faloutsos, C Islands and Bridges: Making Sense of Marked Nodes in Large Graphs. Technical Report CMU-CS-12-124R, Carnegie Mellon University, 2013.
Chau, DH, Akoglu, L, Vreeken, J, Tong, H & Faloutsos, C Interactively and Visually Exploring Tours of Marked Nodes in Large Graphs. Demo at, and included in: Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), ACM, 2012.
Chau, DH, Akoglu, L, Vreeken, J, Tong, H & Faloutsos, C TourViz: Interactive Visualization of Connection Pathways in Large Graphs. Demo at, and included in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 1516-1519, ACM, 2012.