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