2012 · 19 citations · 21 references
ComputingData ScienceData StructuresGraph VisualizationSocial Media AnalyticsData CompressionGraph AlgorithmsGraph AnalyticsGraph TheoryLossless Data CompressionSocial Network AnalysisCompressionGraph CompressionGraph SparsificationGreedy ApproximationGreedy HeuristicsLossless NetworksSequence CompressionSocial Graph Analysis
Compression plays an important role in social network analysis from both practical and theoretical points of view. Although there are a few pioneering studies on social network compression, they mainly focus on lossless approaches. In this paper, we tackle the novel problem of community preserving lossy compression of social networks. The trade-off between space and information preserved in a lossy compression presents an interesting angle for social network analysis, and, at the same time, makes the problem very challenging. We propose a sequence graph compression approach, discuss the design of objective functions towards community preservation, and present an interesting and practically effective greedy algorithm. Our experimental results on both real data sets and synthetic data sets demonstrate the promise of our method.
21
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
Finding community structure in very large networks
Aaron Clauset, M. E. J. Newman, Cristopher Moore · Physical Review E · 2004 · 7.5K citations · Full text