2011 · 120 citations · 8 references
ComputingVisualizationCollective BehaviorCommunity AssessmentComplex SystemsCommunity DetectionCommunity StructureGraph AlgorithmsGraph MiningGraph TheoryNetwork AnalysisCommunity Evaluation MetricsCommunity Quality AssessmentConnectionsEvaluation MetricsGraph Centrality AnalysisMetricsNetwork Community Detection
Community sub graphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In this paper, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs, devising a novel concept of k-cores on weighted graphs. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results.
8
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
The Evolution of Random Graphs
Béla Bollobás · Transactions of the American Mathematical Society · 1984 · 1K citations