IBM Journal of Research and Development · 2013 · 16 citations · 26 references
ComputingComputer ScienceComputer SystemsDistributed SystemsParallel AlgorithmsParallel ComputingCommunity DetectionCommunity StructureData ParallelismDistributed ComputingDistributed Data ProcessingScalable Algorithm DesignMapreduceMapreduce AlgorithmsParallel ProgrammingPostprocessing TechniquesScalable Community DetectionScalable Graph AlgorithmsSimilarity DetectionStorage Space Optimization
In this paper, we present a community-detection solution for massive-scale social networks using MapReduce, a parallel programming framework. We use a similarity metric to model the community probability, and the model is designed to be parallelizable and scalable in the MapReduce framework. More importantly, we propose a set of degree-based preprocessing and postprocessing techniques named DEPOLD (DElayed Processing of Large Degree nodes) that significantly improve both the community-detection accuracy and performance. With DEPOLD, delaying analysis of 1% of high-degree nodes to the postprocessing stage reduces both processing time and storage space by one order of magnitude. DEPOLD can be applied to other graph-clustering problems. Furthermore, we design and implement two similarity calculation algorithms using MapReduce with different computation and communication characteristics in order to adapt to various system configurations. Finally, we conduct experiments with publicly available datasets. Our evaluation demonstrates the effectiveness, efficiency, and scalability of the proposed solution.
26
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text