{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:58:43Z","timestamp":1780635523021,"version":"3.54.1"},"reference-count":28,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T00:00:00Z","timestamp":1658966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Aalto University"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.<\/jats:p>","DOI":"10.3390\/a15080262","type":"journal-article","created":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T03:21:16Z","timestamp":1658978476000},"page":"262","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3677-816X","authenticated-orcid":false,"given":"Vesa","family":"Kuikka","sequence":"first","affiliation":[{"name":"Finnish Defence Research Agency, Tykkikent\u00e4ntie 1, P.O. Box 10, 11311 Riihim\u00e4ki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henrik","family":"Aalto","sequence":"additional","affiliation":[{"name":"Finnish Defence Research Agency, Tykkikent\u00e4ntie 1, P.O. Box 10, 11311 Riihim\u00e4ki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matias","family":"Ij\u00e4s","sequence":"additional","affiliation":[{"name":"Eficode Oy, 00100 Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3805-9687","authenticated-orcid":false,"given":"Kimmo K.","family":"Kaski","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalto University School of Science, P.O. Box 15500, 00076 Aalto, Finland"},{"name":"The Alan Turing Institute, 96 Euston Rd, Kings Cross, London NW1 2DB, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,7,28]]},"reference":[{"key":"ref_1","unstructured":"Barab\u00e1si, A.-L., and P\u00f3sfai, M. (2016). Network Science, Cambridge University Press."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J. (2018). Networks: An Introduction, Oxford University Press.","DOI":"10.1093\/oso\/9780198805090.003.0001"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.physrep.2005.10.009","article-title":"Complex networks: Structure and dynamics","volume":"424","author":"Boccaletti","year":"2006","journal-title":"Phys. Rep."},{"key":"ref_4","unstructured":"Tian, Y., and Lambiotte, R. (2021). Unifying Diffusion Models on Networks and Their Influence Maximisation. CoRR, abs\/2112.01465."},{"key":"ref_5","unstructured":"Luo, Z. (2022, June 29). Network Research: Exploration of Centrality Measures and Network Flows Using Simulation Studies. Available online: essay.utwente.nl\/76847\/1\/LuoMAEEMCS.pdf."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1186\/s40649-018-0060-z","article-title":"Influence spreading model used to analyse social networks and detect sub-communities","volume":"5","author":"Kuikka","year":"2018","journal-title":"Comput. Soc. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"126875","DOI":"10.1016\/j.physa.2022.126875","article-title":"Modelling epidemic spreading in structured organisations","volume":"592","author":"Kuikka","year":"2022","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","article-title":"A Relational Model of Data for Large Shared Data Banks","volume":"13","author":"Codd","year":"1970","journal-title":"Commun. ACM"},{"key":"ref_9","unstructured":"Rogers, E.M. (2003). Diffusion of Innovations, Free Press. [5th ed.]."},{"key":"ref_10","unstructured":"Peralta, A.F., Kert\u00e9sz, J., and I\u00f1iguez, G. (2022, June 29). Opinion Dynamics in Social Networks: From Models to Data. Available online: https:\/\/arxiv.org\/pdf\/2201.01322."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Centola, D. (2018). How Behavior Spreads: The Science of Complex Contagions, Princeton University Press.","DOI":"10.23943\/9781400890095"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"eabf1211","DOI":"10.1126\/sciadv.abf1211","article-title":"Belief propagation for networks with loops","volume":"7","author":"Kirkley","year":"2021","journal-title":"Sci. Adv."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1086\/521848","article-title":"Complex Contagions and the Weakness of Long Ties","volume":"113","author":"Centola","year":"2007","journal-title":"Am. J. Sociol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"10422","DOI":"10.1038\/s41598-018-28615-3","article-title":"Competing contagion processes: Complex contagion triggered by simple contagion","volume":"8","author":"Min","year":"2018","journal-title":"Sci. Rep."},{"key":"ref_15","unstructured":"Ij\u00e4s, M., Levijoki, J., and Kuikka, V. (2018, January 21\u201322). Scalable Algorithm for Computing Influence Spreading Probabilities in Social Networks. Proceedings of the 5th European Conference on Social Media (ECSM 2018), Limerick, Ireland."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the Spread of Influence through a Social Network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD\u201903, Washington, DC, USA.","DOI":"10.1145\/956755.956769"},{"key":"ref_17","unstructured":"Moscato, P., and de Vries, N.J. (2019). Centrality in networks: Finding the most important nodes. Proceedings of the Business and Consumer Analytics: New ideas. Part III, Chapter 8, Springer International Publishing."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.socnet.2004.11.008","article-title":"Centrality and network flow","volume":"27","author":"Borgatti","year":"2005","journal-title":"Soc. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"ref_20","first-page":"16","article-title":"A mathematical model for group structures","volume":"7","author":"Bavelas","year":"1948","journal-title":"Appl. Antropoly"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","article-title":"A set of measures of centrality based on betweenness","volume":"40","author":"Freeman","year":"1977","journal-title":"Sociometry"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","article-title":"Centrality in social networks conceptual clarification","volume":"1","author":"Freeman","year":"1979","journal-title":"Soc. Netw."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: A user guide","volume":"659","author":"Fortunato","year":"2016","journal-title":"Phys. Rep."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_25","unstructured":"Leskovec, J., and Krevl, A. (2022, June 29). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_26","unstructured":"Van de Bunt, G. (1999). Friends by Choice. An Actor-Oriented Statistical Network Model for Friendship Networks through Time. [Ph.D. Thesis, University of Groningen]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0010-4655(02)00201-1","article-title":"The Structure and Function of Complex Networks","volume":"147","author":"Newman","year":"2003","journal-title":"Comput. Phys. Commun."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Cherifi, C., Cherifi, H., Karsai, M., and Musolesi, M. (2018). Influence Spreading Model Used to Community Detection in Social Networks. Proceedings of the Complex Networks & Their Applications VI, Springer International Publishing.","DOI":"10.1007\/978-3-319-72150-7"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/8\/262\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:57:56Z","timestamp":1760140676000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/8\/262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,28]]},"references-count":28,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8]]}},"alternative-id":["a15080262"],"URL":"https:\/\/doi.org\/10.3390\/a15080262","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,28]]}}}