Searching social networks for subgraph patterns

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

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

Abstract

Software tools for Social Network Analysis (SNA) are being developed which support various types of analysis of social networks extracted from social media websites (e.g., Twitter). Once extracted and stored in a database such social networks are amenable to analysis by SNA software. This data analysis often involves searching for occurrences of various subgraph patterns (i.e., graphical representations of entities and relationships). The authors have developed the Graph Matching Toolkit (GMT) which provides an intuitive Graphical User Interface (GUI) for a heuristic graph matching algorithm called the Truncated Search Tree (TruST) algorithm. GMT is a visual interface for graph matching algorithms processing large social networks. GMT enables an analyst to draw a subgraph pattern by using a mouse to select categories and labels for nodes and links from drop-down menus. GMT then executes the TruST algorithm to find the top five occurrences of the subgraph pattern within the social network stored in the database. GMT was tested using a simulated counter-insurgency dataset consisting of cellular phone communications within a populated area of operations in Iraq. The results indicated GMT (when executing the TruST graph matching algorithm) is a time-efficient approach to searching large social networks. GMT's visual interface to a graph matching algorithm enables intelligence analysts to quickly analyze and summarize the large amounts of data necessary to produce actionable intelligence.

Original languageEnglish (US)
Title of host publicationSensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XII
DOIs
StatePublished - Aug 9 2013
Externally publishedYes
EventSensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XII - Baltimore, MD, United States
Duration: Apr 29 2013May 1 2013

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
Volume8711
ISSN (Print)0277-786X
ISSN (Electronic)1996-756X

Other

OtherSensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XII
CountryUnited States
CityBaltimore, MD
Period4/29/135/1/13

Keywords

  • Graph matching
  • Social network analysis
  • Visualization software

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Searching social networks for subgraph patterns'. Together they form a unique fingerprint.

Cite this