2012 · 105 citations · 27 references
ComputingBioinformaticsComputer ScienceComputational BiologyComputational GeometryData MiningGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryNetwork CentralitySocial Network MiningCliquesConnectivity AlgorithmsSubgraph ExtractionSubgraph Mining
In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e. g., social network analysis, bioinformatics, web link research. Compared with other explicit structures for modeling vertex clusters, such as quasi-clique, k-core, which only set the requirement on vertex degrees, k-edge-connected subgraph further requires high connectivity within a subgraph (a stronger requirement), and hence defines a more closely related vertex cluster.
27
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
Jure Leskovec, Jon Kleinberg, Christos Faloutsos · ACM Transactions on Knowledge Discovery from Data · 2007 · 2.5K citations