Mining for Spatially-Near Communities in Geo-Located Social Networks

Abstract

Current approaches to community detection in social networks often ignore the spatial location of the nodes. In this paper, we look to extract spatially-near communities in a social network. We introduce a new metric to measure the quality of a community partition in a geolocated social networks called spatially-near modularity a value that increases based on aspects of the network structure but decreases based on the distance between nodes in the communities. We then look to find an optimal partition with respect to this measure - which should be an ideal community with respect to both social ties and geographic location. Though an NP-hard problem, we introduce two heuristic algorithms that attempt to maximize this measure and outperform nongeographic community finding by an order of magnitude. Applications to counter-terrorism are also discussed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2013
Accession Number
ADA590263

Entities

People

  • Guillermo Hernandez
  • Joseph Hannigan
  • Patrick Roos
  • Paulo Shakarian
  • Richard M. Medina

Organizations

  • United States Military Academy

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Communities
  • Computer Science
  • Computers
  • Counterterrorism
  • Detection
  • Electrical Engineering
  • Engineering
  • Geography
  • Information Operations
  • Network Topology
  • New York
  • Operating Systems
  • Social Networks
  • Sociology
  • Terrorism
  • United States Military Academy

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Political Violence and Terrorism Studies.