February 24, 2015

- 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)

- 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

- 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

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

- 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