Searching social networks for subgraph patterns

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

doi:10.1117/12.2015264

6 June 2013 Searching social networks for subgraph patterns

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

Author Affiliations +

Proceedings Volume 8711, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XII; 87110T (2013) https://doi.org/10.1117/12.2015264
Event: SPIE Defense, Security, and Sensing, 2013, Baltimore, Maryland, United States

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.

Citation Download Citation

Kirk Ogaard, Kirk Ogaard, Sue Kase, Sue Kase, Heather Roy, Heather Roy, Rakesh Nagi, Rakesh Nagi, Kedar Sambhoos, Kedar Sambhoos, Moises Sudit, Moises Sudit, "Searching social networks for subgraph patterns", Proc. SPIE 8711, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense XII, 87110T (6 June 2013); doi: 10.1117/12.2015264; https://doi.org/10.1117/12.2015264

ACCESS THE FULL ARTICLE

PERSONAL SIGN IN
Full access may be available with your subscription

Email or Username Forgot your username?

Password Forgot your password?

Show

Remember Email/Username on this computer

Remember Password

No SPIE account? Create an account
or Institutional Sign In via Shibboleth

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $14.40

Non-members: $18.00 ADD TO CART

Show All Keywords

Keywords/Phrases

Search In:

Publication Years