February 24, 2015


Who cares and why did we make this?


  • Many relationships easily conceptualized as a graph/network
  • A graph is defined as a collection of nodes (entities) and edges (relationships)
  • A community is defined as a group of nodes in a graph that share properties
  • Examples of such relationships include:
    • social networks (sociology)
    • the world wide web (computer science)
    • protein networks (biology)

The Problem

  • Current methodology for community detection often involves an algorithmic approach; partitions a graph into node clusters iteratively before stopping criterion
  • First define an objective function and then optimize
  • Many different objective functions possible, providing many ways to split a graph
  • The optimization of an objective function is typically an NP-hard problem
  • The number of possible partitions of the network requires \(2^n\) complexity

Current Solutions

  • Heuristics used to optimize the objective function in a reasonable amount of time
  • Heuristic-based clustering is useful because this offers an automated way to perform community detection

The main elements of the problem themselves [graph clustering], i.e. the concepts of community and partition, are not rigorously defined, and require some degree of arbitrariness and/or common sense. (Fortunato, 2010)

  • Heuristics are not the solution

Leverage the Human Visual System

  • Communities are often fuzzily-defined human concepts
  • Address this by adding element of human judgement
  • Introduce a novel visualization-based community detection tool, gravicom

gravicom Functionality

  • Allows users to
    • Visually direct and interact with the steps of community detection
    • Assess the created clusters through visual and quantitative summaries
  • Standalone exploratory tool for graph data
  • Initial state to be passed to a community detection algorithm in order reduce the complexity of optimization



  • Shiny: Server-client interaction
  • D3: User interface and graph layout
  • igraph/rjson: Data formatting

Football Example