Document Open Access Logo

Relating Real and Synthetic Social Networks Through Centrality Measures

Authors Maria J. Blesa , Mihail Eduard Popa, Maria Serna

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.7.pdf
  • Filesize: 6.96 MB
  • 21 pages

Document Identifiers

Author Details

Maria J. Blesa
  • Computer Science Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
Mihail Eduard Popa
  • Barcelona School of Informatics, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
Maria Serna
  • Computer Science Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
  • Institute of Mathematics (IMTech), Universitat Politècnica de Catalunya (UPC), Barcelona, Spain

Funding

M. Blesa and M. Serna acknowledge support by MICIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). M.E. Popa was funded by the Ministry of Education and Vocational Training (MEFP) with a student grant (Beca de colaboración, call 2020-2021).

Cite AsGet BibTex

Maria J. Blesa, Mihail Eduard Popa, and Maria Serna. Relating Real and Synthetic Social Networks Through Centrality Measures. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.7

Abstract

We perform here a comparative study on the behaviour of real and synthetic social networks with respect to a selection of nine centrality measures. Some of them are topology based (degree, closeness, betweenness), while others consider the relevance of the actors within the network (Katz, PageRank) or their ability to spread influence through it (Independent Cascade rank, Linear Threshold Rank). We run different experiments on synthetic social networks, with 1K, 10K, and 100K nodes, generated according to the Gaussian Random partition model, the stochastic block model, the LFR benchmark graph model and hyperbolic geometric graphs model. Some real social networks are also considered, with the aim of discovering how do they relate to the synthetic models in terms of centrality. Apart from usual statistical measures, we perform a correlation analysis between all the nine measures. Our results indicate that, in general, the correlation matrices of the different models scale nicely with size. Moreover, the correlation plots distinguish four categories that classify most of the real networks studied here. Those categories have a clear correspondence with particular configurations of the models for synthetic networks.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Networks → Network dynamics
Keywords
  • centrality measures
  • influence spread models
  • synthetic social networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. M.J. Blesa, P. García-Rodríguez, and M.Serna. Forward and backward linear threshold ranks. In International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 265-269. ACM, 2021. URL: https://doi.org/10.1145/3487351.3488355.
  2. L. Ceriani and P. Verme. The origins of the Gini index: extracts from Variabilità e Mutabilità (1912) by Corrado Gini. The Journal of Economic Inequality, 10(3):421-443, 2012. Google Scholar
  3. Hocine Cherifi, Gergely Palla, Boleslaw K. Szymanski, and Xiaoyan Lu. On community structure in complex networks: challenges and opportunities. Applied Network Science, 4(117):2364-8228, 2019. URL: https://doi.org/10.1007/s41109-019-0238-9.
  4. X. Molinero F. Riquelme, P. Gonzalez-Cantergiani and M. Serna. Centrality measures in social networks based on linear threshold model. Knowledge-Based Systems, 40:92-102, 2017. URL: https://doi.org/10.1016/j.knosys.2017.10.029.
  5. L.C Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35-41, 1977. Google Scholar
  6. C. Gini. Variabilitàe Mutuabilità. Contributo allo Studio delle Distribuzioni e delle Relazioni Statistiche. C. Cuppini, 1912. Google Scholar
  7. J. Goldenberg, B. Libai, and E. Muller. Using complex systems analysis to advance marketing theory development. Technical Report, Academy of Marketing Science Review, 2001. Google Scholar
  8. L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18:39-43, 1953. Google Scholar
  9. D. Kempe, J.M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. Proceedings of the 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 137-146, 2003. Google Scholar
  10. D. Kempe, J.M. Kleinberg, and É. Tardos. Influential nodes in a diffusion model for social networks. In Intl. Colloquium on Automata, Languages and Programming (ICALP), volume 3580, pages 1127-1138. Lecture Notes in Computer Science, 2005. URL: https://doi.org/10.1007/11523468_91.
  11. M. Kendall. A new measure of rank correlation. Biometrika, 30:81-93, 1938. Google Scholar
  12. D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E Stat. Nonlin. Soft Matter Phys., 82((3 Pt 2):036106), 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  13. A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 78:046110, October 2008. URL: https://doi.org/10.1103/PhysRevE.78.046110.
  14. NetworkX. Gaussian Random Partition Graph. Accessed: 2022-02. URL: https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.gaussian_random_partition_graph.html.
  15. NetworkX. LFR Benchmark Graph. Accessed: 2022-02. URL: https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.LFR_benchmark_graph.html.
  16. NetworkX. Stochastic Block Model. Accessed: 2022-02. URL: https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.stochastic_block_model.html.
  17. Mark E.J. Newman. Networks: An introduction. Oxford University Press, 2010. URL: https://doi.org/10.1093/acprof:oso/9780199206650.001.0001.
  18. S. Oldham, B. Fulcher, L. Parkes, A. Arnatkevic̆iūté, C. Suo, and A. Fornito. Consistencies and differences between centrality measures across distinct classes of networks. PLoS ONE, 14(7):0220061, 2019. URL: https://doi.org/10.1371/journal.pone.0220061.
  19. L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web, technical report. Stanford Digital Library, 1999. Google Scholar
  20. K. Blackmond Laskey P.W. Holland and S. Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-137, 1983. URL: https://doi.org/10.1016/0378-8733(83)90021-7.
  21. C. Orsini R. Aldecoa and D. Krioukov. Hyperbolic graph generator. Computer Physics Communications, 196:492-496, 2015. URL: https://doi.org/10.1016/j.cpc.2015.05.028.
  22. C. Sciarra, G. Chiarotti, F. Laio, and L. Ridolfi. A change of perspective in network centrality. Scientific Reports, 2018. URL: https://doi.org/10.1038/s41598-018-33336-8.
  23. P. Shakarian, A. Bhatnagar, A. Aleali, E. Shaabani, and R. Guo. The Independent Cascade and Linear Threshold Models, chapter 4, pages 35-48. Briefs in Computer Science. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-23105-1_4.
  24. C. Spearman. The proof and measurement of association between two things. AM. J. Psychol, 15:88-103, 1904. Google Scholar
  25. D. Wagner U. Brandes, M. Gaertler. Experiments on graph clustering algorithms. In Algorithms - ESA 2003, pages 568-579. Springer Berlin Heidelberg, 2003. Google Scholar
  26. T.W. Valente, K. Corognes, C. Lakon, and E. Costenbader. How correlated are network centrality measures? Connections, 28(1):16-26, 2008. Google Scholar
  27. S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact