Structure-Preserving Sparsification of Social Networks

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.

References

1. 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.
2. 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.
3. 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.
4. 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
5. 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.
6. 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.abstract
7. C. Staudt, A. Sazonovs, and H. Meyerhenke, "Networkit: An interactive tool suite for high-performance network analysis," CoRR, vol. abs/1403.3005, 2014.
8. M. Newman, Networks: an introduction. Oxford University Press, 2010.
9. 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=Ha2aBqS415YC
10. 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
11. 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
12. 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
13. 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.
14. 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
15. 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_9
16. 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.
17. 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#BastianHJ09
18. 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.046110
19. 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.
20. 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.

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

• Information systems

  • Information systems applications

• Mathematics of computing

  • Discrete mathematics