Chaos An Interdisciplinary Journal of Nonlinear Science · 2009 · 39 citations · 5 references
ComputingVisualizationGraph VisualizationNetwork VisualizationScientific VisualizationCommunity DetectionCommunity StructureCommunity VisualizationGraph Layout AlgorithmsGraph TheoryNetwork ModularityCommunity Structure VisualizationLayout AlgorithmsLayout Optimization AlgorithmsModularity OptimizationNetwork Community StructureSpectral Optimization
Network analysis provides powerful tools for studying interactions (represented by edges) between a large number of entities (nodes). Various methods can be used to identify subgraphs known as communities, which are groups of nodes that are densely connected to each other.1 Because networks can be large, coarse-graining into communities facilitates subsequent investigation of structural organization. The field of graph visualization is enormous,2 so we restrict our attention to modifying the Kamada–Kawai3 (KK) and Fruchterman–Reingold4 (FR) force-directed layout algorithms to include community information. FR is closely related to modularity maximization,5 one of the main approaches employed for identifying communities. However, it does not resolve the community structure when the number of communities exceeds the spatial dimension of visualization (the usual case). We incorporate a specified community structure (however obtained) into similar layouts. In our visualizations,6 we identified communities of the largest connected components of graphs using a spectral modularity-optimization algorithm.7 We place the centers of these communities using FR, treating communities as the nodes of a (significantly smaller) network with rescaled intercommunity links. We use KK to obtain relative placements of nodes within each community (ignoring intercommunity links). Combining these coordinates, we then use the same KK force rules to rotate (and flip, if necessary) individual communities for optimal placement relative to nodes in the other communities (including intercommunity links), maintaining the specified community center positions. We illustrate our procedure with three examples in Fig. Fig.1.1. On the left is a graph of network scientists connected by paper co-authorship,7 colored by a community assignment. On the right are Facebook networks, defined by self-identified, reciprocal online friendships:8 the Caltech network colored by ‘‘House’’ (dorm) affiliation (top); and the Haverford network colored by class year (bottom). Similarly positioned community-level pie charts further illustrate the demographic organization of the Facebook networks.9 Figure 1
5
An algorithm for drawing general undirected graphs
Tomihisa Kamada, Satoru Kawai · Information Processing Letters · 1989 · 2.8K citations
Modularity clustering is force-directed layout
Andreas Noack · Physical Review E · 2009 · 254 citations · Full text
Community Structure in Online Collegiate Social Networks
Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha et al. · arXiv (Cornell University) · 2008 · 45 citations · Full text