ABSTRACT
Sparsification reduces the size of networks while preserving structural and statistical properties of interest. Various sparsifying algorithms have been proposed in different contexts. We contribute the first systematic conceptual and experimental comparison of edge sparsification methods on a diverse set of network properties. It is shown that they can be understood as methods for rating edges by importance and then filtering globally by these scores. In addition, we propose a new sparsification method (Local Degree) which preserves edges leading to local hub nodes. All methods are evaluated on a set of 100 Facebook social networks with respect to network properties including diameter, connected components, community structure, and multiple node centrality measures. Experiments with our implementations of the sparsification methods (using the open-source network analysis tool suite NetworKit) show that many network properties can be preserved down to about 20% of the original set of edges. Furthermore, the experimental results allow us to differentiate the behavior of different methods and show which method is suitable with respect to which property. Our Local Degree method is fast enough for large-scale networks and performs well across a wider range of properties than previously proposed methods.
- L. d. F. Costa, O. N. Oliveira Jr, G. Travieso, F. A. Rodrigues, P. R. Villas Boas, L. Antiqueira, M. P. Viana, and L. E. Correa Rocha, "Analyzing and modeling real-world phenomena with complex networks: a survey of applications," Advances in Physics, vol. 60, no. 3, pp. 329--412, 2011.Google ScholarCross Ref
- J. Batson, D. A. Spielman, N. Srivastava, and S.-H. Teng, "Spectral sparsification of graphs: theory and algorithms," communications of the ACM, vol. 56, no. 8, pp. 87--94, 2013. Google ScholarDigital Library
- N. K. Ahmed, J. Neville, and R. Kompella, "Network sampling: From static to streaming graphs," ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 8, no. 2, p. 7, 2014. Google ScholarDigital Library
- J. Leskovec and C. Faloutsos, "Sampling from large graphs," in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '06. New York, NY, USA: ACM, 2006, pp. 631--636. {Online}. Available: http://doi.acm.org/10.1145/1150402.1150479 Google ScholarDigital Library
- P. Ebbes, Z. Huang, A. Rangaswamy, H. P. Thadakamalla, and O. R. G. B. Unit, "Sampling large-scale social networks: Insights from simulated networks," in 18th Annual Workshop on Information Technologies and Systems, Paris, France. Citeseer, 2008.Google Scholar
- M. Á. Serrano, M. Boguñá, and A. Vespignani, "Extracting the multiscale backbone of complex weighted networks," Proceedings of the National Academy of Sciences, vol. 106, no. 16, pp. 6483--6488, 2009. {Online}. Available: http://www.pnas.org/content/106/16/6483.abstractGoogle ScholarCross Ref
- C. Staudt, A. Sazonovs, and H. Meyerhenke, "Networkit: An interactive tool suite for high-performance network analysis," CoRR, vol. abs/1403.3005, 2014.Google Scholar
- M. Newman, Networks: an introduction. Oxford University Press, 2010. Google ScholarCross Ref
- G. Simmel and K. Wolff, The Sociology of Georg Simmel, ser. Free Press paperback. Free Press, 1950. {Online}. Available: http://books.google.de/books?id=Ha2aBqS415YCGoogle Scholar
- M. Ortmann and U. Brandes, "Triangle listing algorithms: Back from the diversion," in 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, C. C. McGeoch and U. Meyer, Eds. SIAM, 2014, pp. 1--8. {Online}. Available: http://dx.doi.org/10.1137/1.9781611973198.1 Google ScholarDigital Library
- N. Chiba and T. Nishizeki, "Arboricity and subgraph listing algorithms," SIAM Journal on Computing, vol. 14, no. 1, pp. 210--223, 1985. {Online}. Available: http://epubs.siam.org/doi/abs/10.1137/0214017 Google ScholarDigital Library
- V. Satuluri, S. Parthasarathy, and Y. Ruan, "Local graph sparsification for scalable clustering," in Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD '11. New York, NY, USA: ACM, 2011, pp. 721--732. {Online}. Available: http://doi.acm.org/10.1145/1989323.1989399 Google ScholarDigital Library
- T. Saha, H. Rangwala, and C. Domeniconi, "Sparsification and sampling of networks for collective classification," in Social Computing, Behavioral-Cultural Modeling and Prediction. Springer, 2013, pp. 293--302. Google ScholarDigital Library
- B. Nick, C. Lee, P. Cunningham, and U. Brandes, "Simmelian backbones: Amplifying hidden homophily in facebook networks," in Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ser. ASONAM '13. New York, NY, USA: ACM, 2013, pp. 525--532. {Online}. Available: http://doi.acm.org/10.1145/2492517.2492569 Google ScholarDigital Library
- A. Nocaj, M. Ortmann, and U. Brandes, "Untangling hairballs - from 3 to 14 degrees of separation," in Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014, Revised Selected Papers, ser. Lecture Notes in Computer Science, C. A. Duncan and A. Symvonis, Eds., vol. 8871. Springer, 2014, pp. 101--112. {Online}. Available: http://dx.doi.org/10.1007/978-3-662-45803-7_9Google ScholarDigital Library
- C. Staudt and H. Meyerhenke, "Engineering parallel algorithms for community detection in massive networks," Parallel and Distributed Systems, IEEE Transactions on, vol. PP, no. 99, pp. 1--1, 2015.Google Scholar
- M. Bastian, S. Heymann, and M. Jacomy, "Gephi: An open source software for exploring and manipulating networks." in ICWSM, E. Adar, M. Hurst, T. Finin, N. S. Glance, N. Nicolov, and B. L. Tseng, Eds. The AAAI Press, 2009. {Online}. Available: http://dblp.uni-trier.de/db/conf/icwsm/icwsm2009.html#BastianHJ09Google Scholar
- A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Phys. Rev. E, vol. 78, p. 046110, Oct 2008. {Online}. Available: http://link.aps.org/doi/10.1103/PhysRevE.78.046110Google ScholarCross Ref
- A. L. Traud, P. J. Mucha, and M. A. Porter, "Social structure of facebook networks," Physica A: Statistical Mechanics and its Applications, vol. 391, no. 16, pp. 4165--4180, 2012.Google ScholarCross Ref
- S. Fortunato, M. Boguñá, A. Flammini, and F. Menczer, "Approximating pagerank from in-degree," in Algorithms and Models for the Web-Graph. Springer, 2008, pp. 59--71. Google ScholarDigital Library
- Structure-Preserving Sparsification of Social Networks
Recommendations
A novel measure of edge centrality in social networks
The problem of assigning centrality values to nodes and edges in graphs has been widely investigated during last years. Recently, a novel measure of node centrality has been proposed, called @k-path centrality index, which is based on the propagation of ...
A Sparsification Technique for Faster Hierarchical Community Detection in Social Networks
ICECCS '14: Proceedings of the 2014 3rd International Conference on Eco-friendly Computing and Communication SystemsThe proliferation of social networking sites and their rapidly growing user-base have made information sharing simpler than ever before. However, a typical social network user might get easily overloaded with information that may not be of interest to ...
Distributed Assessment of Network Centralities in Complex Social Networks
ASONAM '12: Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012)We present our ongoing work towards a framework for the Distributed Assessment of Network Centralities (DANCE) in complex networks. DANCE targets the efficient evaluation of the network centrality based only on localized information, restricted to a ...
Comments