Graph Mining

Subgraph Matching for Dynamic Graphs

Contact Student: Sutanay Choudhury, sutanay.choudhury@email.wsu.edu

Webpage: http://www.linkedin.com/in/sutanay

Details:

The objective of this research is to develop techniques for subgraph matching in the context of dynamic graphs, datasets that represent temporal evolution of relationship between entities.  We are investigating applications of approximate graph matching algorithms with a strong focus on scalability on multi-core or massively multithreaded architectures.

Datasets:

http://law.dsi.unimi.it/datasets.php

http://socialnetworks.mpi-sws.org/

Relevant Publications:

 

- Approximate Constrained Subgraph Matching, St├ęphane Zampelli, Yves Deville and Pierre Dupont, PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005

- SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs, Shije Zhang, Jiong Yang, Wei Jin, PVLDB 2010

- TALE: A Tool for Approximate Large Graph Matching, Yuanyuan Tian, Jignesh M. Patel, ICDE 2008

- A new algorithm for error-tolerant subgraph isomorphism detection, Messmer, B.T. and Bunke, H., IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998

- Chin, G.; Marquez, A.; Choudhury, S.; Maschhoff, K. "Implementing and evaluating multithreaded triad census algorithms on the Cray XMT," IEEE International Symposium on  Parallel&  Distributed Processing, 2009.

 

Relevant Resources:

- http://www.graph500.org