research-article

Open access

Social influence under improved multi-objective metaheuristics

Authors:

Fabian Riquelme,

Francisco Muñoz,

Rodrigo OlivaresAuthors Info & Claims

ASONAM '21: Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Pages 479 - 486

https://doi.org/10.1145/3487351.3488558

Published: 19 January 2022 Publication History

Abstract

The influence maximization problem (IMP) and the least cost influence problem (LCI) are two relevant and widely studied problems in social network analysis. The first one consists of maximizing the influence spread in a social network, starting with a given seed size of actors; the second one consists of minimizing the seed set to reach a given number of influenced nodes. Recently, both problems have been studied together with a multi-objective metaheuristic approach. In this work, diffusion filter restrictions based on the network topology are proposed to reduce the search space and thus improving the convergence speed of the solutions. This proposal allows increasing the quality of the results. As the influence spread model, the Linear Threshold model will be used. The solution is tested in three social networks of different sizes, finding promising improvements in harder instances.

References

[1]

D. Easley and J. Kleinberg, Networks, Crowds, and Markets. Cambridge University Press, Jul. 2010.

[2]

D. Gruhl, D. Liben-Nowell, R. Guha, and A. Tomkins, "Information diffusion through blogspace," ACM SIGKDD Explorations Newsletter, vol. 6, no. 2, pp. 43--52, Dec. 2004.

Digital Library

[3]

X. Song, B. L. Tseng, C.-Y. Lin, and M.-T. Sun, "Personalized recommendation driven by information flow," in Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR'06. ACM Press, 2006, pp. 509--516.

[4]

X. Zhang, J. Zhu, Q. Wang, and H. Zhao, "Identifying influential nodes in complex networks with community structure," Knowledge-Based Systems, vol. 42, pp. 74--84, Apr. 2013.

Digital Library

[5]

J. Li, W. Peng, T. Li, T. Sun, Q. Li, and J. Xu, "Social network user influence sense-making and dynamics prediction," Expert Systems with Applications, vol. 41, no. 11, pp. 5115--5124, Sep. 2014.

[6]

F. Morone and H. A. Makse, "Influence maximization in complex networks through optimal percolation," Nature, vol. 524, no. 7563, pp. 65--68, Jul. 2015.

[7]

X. Molinero, F. Riquelme, and M. Serna, "Cooperation through social influence," European Journal of Operational Research, vol. 242, no. 3, pp. 960--974, May 2015.

[8]

N. Cassavia, E. Masciari, C. Pulice, D. Sacca, and I. Trubitsyna, "Evaluating the influence of user searches on neighbors," in 2018 IEEE 27th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE). IEEE, Jun. 2018, pp. 165--170.

[9]

X. Molinero, F. Riquelme, and M. Serna, "Measuring satisfaction and power in influence based decision systems," Knowledge-Based Systems, vol. 174, pp. 144--159, Jun. 2019.

Digital Library

[10]

F. Riquelme, P. Gonzalez-Cantergiani, X. Molinero, and M. Serna, "The neighborhood role in the linear threshold rank on social networks," Physica A: Statistical Mechanics and its Applications, vol. 528, p. 121430, Aug. 2019.

[11]

P. M. Domingos and M. Richardson, "Mining the network value of customers," in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, San Francisco, CA, USA, August 26-29, 2001, D. Lee, M. Schkolnick, F. J. Provost, and R. Srikant, Eds. ACM, 2001, pp. 57--66.

[12]

D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD'03. ACM Press, 2003, pp. 137--146.

[13]

M. Granovetter, "Threshold models of collective behavior," American Journal of Sociology, vol. 83, no. 6, pp. 1420--1443, May 1978.

[14]

T. Schelling, Micromotives and Macrobehavior. Norton, 1978.

[15]

D. T. Nguyen, S. Das, and M. T. Thai, "Influence maximization in multiple online social networks," in 2013 IEEE Global Communications Conference (GLOBECOM). IEEE, Dec. 2013, pp. 3060--3065.

[16]

C. Long and R. C.-W. Wong, "Minimizing seed set for viral marketing," in 2011 IEEE 11th International Conference on Data Mining. IEEE, Dec. 2011, pp. 427--436.

[17]

R. Olivares, F. Muñoz, and F. Riquelme, "A multi-objective linear threshold influence spread model solved by swarm intelligence-based methods," Knowledge-Based Systems, vol. 212, p. 106623, Jan. 2021.

[18]

N. E. Karkalos, A. P. Markopoulos, and J. P. Davim, "Swarm intelligence-based methods," in Computational Methods for Application in Industry 4.0. Springer International Publishing, May 2018, pp. 33--55.

[19]

B. Crawford, R. Soto, E. Monfroy, C. Castro, W. Palma, and F. Paredes, "A hybrid soft computing approach for subset problems," Mathematical Problems in Engineering, vol. 2013, pp. 1--12, 2013.

[20]

F. Muñoz, R. Olivares, and F. Riquelme, "Swarm intelligence algorithms for multi-objective IMP," 2020. [Online].

[21]

S. Wasserman, Social network analysis: Methods and applications. Cambridge New York: Cambridge University Press, 1994.

[22]

J.-H. Cho, Y. Wang, I.-R. Chen, K. S. Chan, and A. Swami, "A survey on modeling and optimizing multi-objective systems," IEEE Communications Surveys & Tutorials, vol. 19, no. 3, pp. 1867--1901, 2017.

Digital Library

[23]

A. P. Wierzbicki, "A mathematical basis for satisficing decision making," Mathematical Modelling, vol. 3, no. 5, pp. 391--405, 1982.

[24]

J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of ICNN'95 - International Conference on Neural Networks. IEEE, 1995, pp. 1942--1948.

[25]

R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. IEEE, 1995, pp. 39--43.

[26]

F. Riquelme and P. González-Cantergiani, "Measuring user influence on Twitter: A survey," Information Processing & Management, vol. 52, no. 5, pp. 949--975, Sep. 2016.

Digital Library

[27]

X. Molinero, F. Riquelme, and M. Serna, "Power indices of influence games and new centrality measures for agent societies and social networks," in Ambient Intelligence - Software and Applications. Springer International Publishing, 2014, pp. 23--30.

[28]

R. A. Rossi and N. K. Ahmed, "The network data repository with interactive graph analytics and visualization," in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, ser. AAAI'15. AAAI Press, 2015, pp. 4292--4293.

[29]

S. Kumar, F. Spezzano, V. S. Subrahmanian, and C. Faloutsos, "Edge weight prediction in weighted signed networks," in 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, Dec. 2016, pp. 221--230.

[30]

S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, "REV2," in Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining - WSDM'18. ACM Press, 2018, pp. 333--341.

[31]

M. D. Domenico, A. Lima, P. Mougel, and M. Musolesi, "The anatomy of a scientific rumor," Scientific Reports, vol. 3, no. 1, Oct. 2013.

Cited By

Riquelme FMuñoz FOlivares R(2024)On the max–min influence spread problemApplied Soft Computing10.1016/j.asoc.2024.111343154:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111343
Riquelme FMuñoz FOlivares R(2023)A depth-based heuristic to solve the multi-objective influence spread problem using particle swarm optimizationOPSEARCH10.1007/s12597-023-00662-z60:3(1267-1285)Online publication date: 20-Jun-2023
https://doi.org/10.1007/s12597-023-00662-z

Index Terms

Social influence under improved multi-objective metaheuristics

Index terms have been assigned to the content through auto-classification.

Recommendations

Influence Maximization in Online Social Networks
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining

Starting with the earliest studies showing that the spread of new trends, information, and innovations is closely related to the social influence exerted on people by their social networks, the research on social influence theory took off, providing ...
Models and algorithms for social influence analysis
WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining

Social influence is the behavioral change of a person because of the perceived relationship with other people, organizations and society in general. Social influence has been a widely accepted phenomenon in social networks for decades. Many applications ...
On the max–min influence spread problem: A multi-objective optimization approach ▪
Abstract
A central problem in network dynamics is understanding how influence spreads through a social network. This problem can be studied from an optimization approach. The aim is to find an initial seed of actors, with certain size restrictions, ...
Highlights
- We define the max–min influence spread problem as multi-objective optimization.
- We solve it using swarm intelligence-based methods on real social networks.
- The PSO algorithm allows efficient solution sets with non trivial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '21: Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

November 2021

693 pages

ISBN:9781450391283

DOI:10.1145/3487351

Editors:
Michele Coscia
IT University of Copenhagen, Denmark
,
Alfredo Cuzzocrea
University of Calabria, Italy
,
Kai Shu
Illinois Institute of Technology
,
General Chairs:
Ralf Klamma
RWTH Aachen University, Germany
,
Sharyn O'Halloran
Columbia University
,
Jon Rokne
University of Calgary, Canada

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution-ShareAlike International 4.0 License.

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 January 2022

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Fondecyt de Iniciación, ANID, Chile

Conference

ASONAM '21

Sponsor:

SIGKDD

ASONAM '21: International Conference on Advances in Social Networks Analysis and Mining

November 8 - 11, 2021

Virtual Event, Netherlands

Acceptance Rates

ASONAM '21 Paper Acceptance Rate 22 of 118 submissions, 19%;

Overall Acceptance Rate 116 of 549 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Riquelme FMuñoz FOlivares R(2024)On the max–min influence spread problemApplied Soft Computing10.1016/j.asoc.2024.111343154:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111343
Riquelme FMuñoz FOlivares R(2023)A depth-based heuristic to solve the multi-objective influence spread problem using particle swarm optimizationOPSEARCH10.1007/s12597-023-00662-z60:3(1267-1285)Online publication date: 20-Jun-2023
https://doi.org/10.1007/s12597-023-00662-z

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents