Discovering patterns in social networks with graph matching algorithms

Kirk Ogaard, Heather Roy, Sue Kase, Rakesh Nagi, Kedar Sambhoos, Moises Sudit

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


Social media data are amenable to representation by directed graphs. A node represents an entity in the social network such as a person, organization, location, or event. A link between two nodes represents a relationship such as communication, participation, or financial support. When stored in a database, these graphs can be searched and analyzed for occurrences of various subgraph patterns of nodes and links. This paper describes an interactive visual interface for constructing subgraph patterns called the Graph Matching Toolkit (GMT). GMT searches for subgraph patterns using the Truncated Search Tree (TruST) graph matching algorithm. GMT enables an analyst to draw a subgraph pattern and assign labels to nodes and links using a mouse and drop-down menus. GMT then executes the TruST algorithm to find subgraph pattern occurrences within the directed graph. Preliminary results using GMT to analyze a simulated collection of text communications containing a terrorist plot are reported.

Original languageEnglish (US)
Title of host publicationSocial Computing, Behavioral-Cultural Modeling and Prediction - 6th International Conference, SBP 2013, Proceedings
Number of pages9
StatePublished - Mar 14 2013
Externally publishedYes
Event6th International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction, SBP 2013 - Washington, DC, United States
Duration: Apr 2 2013Apr 5 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7812 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction, SBP 2013
Country/TerritoryUnited States
CityWashington, DC


  • graph matching
  • social network analysis
  • visualization software

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Discovering patterns in social networks with graph matching algorithms'. Together they form a unique fingerprint.

Cite this