research-article

Social Influence Computation and Maximization in Signed Networks with Competing Cascades

Authors:

Ajitesh Srivastava,

Charalampos Chelmis,

Viktor K. PrasannaAuthors Info & Claims

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

Pages 41 - 48

https://doi.org/10.1145/2808797.2809304

Published: 25 August 2015 Publication History

Abstract

Often in marketing, political campaigns and social media, two competing products or opinions propagate over a social network. Studying social influence in such competing cascades scenarios enables building effective strategies for maximizing the propagation of one process by targeting the most "influential" nodes in the network. The majority of prior work however, focuses on unsigned networks where individuals adopt the opinion of their neighbors with certain probability. In real life, relationships between individuals can be positive (e.g., friend of relationship) or negative (e.g. connection between "foes"). According to social theory, people tend to have similar opinions to their friends but opposite of their foes. In this work, we study the problem of competing cascades on signed networks, which has been relatively unexplored. Particularly, we study the progressive propagation of two competing cascades in a signed network under the Independent Cascade Model, and provide an approximate analytical solution to compute the probability of infection of a node at any given time. We leverage our analytical solution to the problem of competing cascades in signed networks to develop a heuristic for the influence maximization problem. Unlike prior work, we allow the seed-set to be initialized with populations of both cascades with the end goal of maximizing the spread of one cascade. We validate our approach on several large-scale real-world and synthetic networks. Our experiments demonstrate that our influence maximization heuristic significantly outperforms state-of-the-art methods, particularly when the network is dominated by distrust relationships.

References

[1]

C. Chelmis and V. K. Prasanna, "The role of organization hierarchy in technology adoption at the workplace," in Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ACM, 2013, pp. 8--15.

Digital Library

[2]

A. Srivastava, C. Chelmis, and V. K. Prasanna, "Influence in social networks: A unified model?" in Advances in Social Networks Analysis and Mining (ASONAM), 2014 IEEE/ACM International Conference on. IEEE, 2014, pp. 451--454.

[3]

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. ACM, 2003, pp. 137--146.

Digital Library

[4]

C. Budak, D. Agrawal, and A. El Abbadi, "Diffusion of information in social networks: Is it all local?" in ICDM, 2012, pp. 121--130.

Digital Library

[5]

C. Chelmis, A. Srivastava, and V. K. Prasanna, "Computational models of technology adoption at the workplace," Social Network Analysis and Mining, vol. 4, no. 1, pp. 1--18, 2014.

[6]

J. Leskovec, D. Huttenlocher, and J. Kleinberg, "Signed networks in social media," in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2010, pp. 1361--1370.

Digital Library

[7]

Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang, "Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships," in Proceedings of the sixth ACM international conference on Web search and data mining. ACM, 2013, pp. 657--666.

Digital Library

[8]

D. Li, Z.-M. Xu, N. Chakraborty, A. Gupta, K. Sycara, and S. Li, "Polarity related influence maximization in signed social networks," PloS one, vol. 9, no. 7, p. e102199, 2014.

[9]

S. Bharathi, D. Kempe, and M. Salek, "Competitive influence maximization in social networks," in Internet and Network Economics. Springer, 2007, pp. 306--311.

Digital Library

[10]

A. Borodin, Y. Filmus, and J. Oren, "Threshold models for competitive influence in social networks," in Internet and network economics. Springer, 2010, pp. 539--550.

Digital Library

[11]

X. He, G. Song, W. Chen, and Q. Jiang, "Influence blocking maximization in social networks under the competitive linear threshold model." in SDM. SIAM, 2012, pp. 463--474.

[12]

P. 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. ACM, 2001, pp. 57--66.

Digital Library

[13]

W. Chen, W. Lu, and N. Zhang, "Time-critical influence maximization in social networks with time-delayed diffusion process," arXiv preprint arXiv:1204.3074, 2012.

[14]

W. Chen, C. Wang, and Y. Wang, "Scalable influence maximization for prevalent viral marketing in large-scale social networks," in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010, pp. 1029--1038.

Digital Library

[15]

W. Chen, Y. Wang, and S. Yang, "Efficient influence maximization in social networks," in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009, pp. 199--208.

Digital Library

[16]

A. Goyal, W. Lu, and L. V. Lakshmanan, "Simpath: An efficient algorithm for influence maximization under the linear threshold model," in Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011, pp. 211--220.

Digital Library

[17]

W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincon, X. Sun, Y. Wang, W. Wei, and Y. Yuan, "Influence maximization in social networks when negative opinions may emerge and propagate." in SDM, vol. 11. SIAM, 2011, pp. 379--390.

[18]

D. Easley and J. Kleinberg, Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.

[19]

N. Pathak, A. Banerjee, and J. Srivastava, "A generalized linear threshold model for multiple cascades," in Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010, pp. 965--970.

Digital Library

[20]

S. A. Myers and J. Leskovec, "Clash of the contagions: Cooperation and competition in information diffusion." in ICDM, vol. 12. Citeseer, 2012, pp. 539--548.

Digital Library

Cited By

Chen HYang DLee WYu PChen M(2023)CMINet: a Graph Learning Framework for Content-aware Multi-channel Influence DiffusionProceedings of the ACM Web Conference 202310.1145/3543507.3583465(545-555)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583465
Jose SVicter Paul P(2023)A survey on identification of influential users in social media networks using bio inspired algorithmsProcedia Computer Science10.1016/j.procs.2023.01.187218:C(2110-2122)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.procs.2023.01.187
Zareie ASakellariou R(2023)Influence maximization in social networks: a survey of behaviour-aware methodsSocial Network Analysis and Mining10.1007/s13278-023-01078-913:1Online publication date: 25-Apr-2023
https://doi.org/10.1007/s13278-023-01078-9
Show More Cited By

Social Influence Computation and Maximization in Signed Networks with Competing Cascades
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
2. Information systems
  1. Information systems applications

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 ...
Influence and correlation in social networks
KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

In many online social systems, social ties between users play an important role in dictating their behavior. One of the ways this can happen is through social influence, the phenomenon that the actions of a user can induce his/her friends to behave in a ...
Towards Understanding Social Influence in On-Line Social Networks
CSCI '14: Proceedings of the 2014 International Conference on Computational Science and Computational Intelligence - Volume 02

On-line social network sites provide an excellent platform for studying social influence among on-line friends. One of the crucial factors in analyzing social influence is conformity. Conformity can be defined as the act of matching attitudes, beliefs, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

August 2015

835 pages

ISBN:9781450338547

DOI:10.1145/2808797

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

ASONAM '15

Sponsor:

SIGKDD

ASONAM '15: Advances in Social Networks Analysis and Mining 2015

August 25 - 28, 2015

Paris, France

Acceptance Rates

Overall Acceptance Rate 116 of 549 submissions, 21%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
296
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen HYang DLee WYu PChen M(2023)CMINet: a Graph Learning Framework for Content-aware Multi-channel Influence DiffusionProceedings of the ACM Web Conference 202310.1145/3543507.3583465(545-555)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583465
Jose SVicter Paul P(2023)A survey on identification of influential users in social media networks using bio inspired algorithmsProcedia Computer Science10.1016/j.procs.2023.01.187218:C(2110-2122)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.procs.2023.01.187
Zareie ASakellariou R(2023)Influence maximization in social networks: a survey of behaviour-aware methodsSocial Network Analysis and Mining10.1007/s13278-023-01078-913:1Online publication date: 25-Apr-2023
https://doi.org/10.1007/s13278-023-01078-9
Hai-Jew S(2022)Self-Presenting Virtually for Remote Social InfluencePractical Peer-to-Peer Teaching and Learning on the Social Web10.4018/978-1-7998-6496-7.ch013(407-461)Online publication date: 2022
https://doi.org/10.4018/978-1-7998-6496-7.ch013
Manrique de Lara AKorutcheva E(2022)Political Signed Temporal Networks: A Deep Learning ApproachAxioms10.3390/axioms1109046411:9(464)Online publication date: 8-Sep-2022
https://doi.org/10.3390/axioms11090464
Tomar ADhiman AMidha A(2022)Ranking Users in the Social Network: A Survey of Budget and Opinion dependent Methods2022 International Conference on Sustainable Computing and Data Communication Systems (ICSCDS)10.1109/ICSCDS53736.2022.9760915(1055-1060)Online publication date: 7-Apr-2022
https://doi.org/10.1109/ICSCDS53736.2022.9760915
Chen BJiang WChen YChen LWang RHan SLin JZhang Y(2022)Influence blocking maximization on networks: Models, methods and applicationsPhysics Reports10.1016/j.physrep.2022.05.003976(1-54)Online publication date: Sep-2022
https://doi.org/10.1016/j.physrep.2022.05.003
Terizi CChatzakou DPitoura ETsaparas PKourtellis N(2021)Modeling aggression propagation on social mediaOnline Social Networks and Media10.1016/j.osnem.2021.10013724(100137)Online publication date: Jul-2021
https://doi.org/10.1016/j.osnem.2021.100137
Sung CMa HHuang J(2020)Positive Influence Maximization and Negative Influence Minimization in Signed Networks under Competitive Independent Cascade Model2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA49011.2020.00036(236-244)Online publication date: Oct-2020
https://doi.org/10.1109/DSAA49011.2020.00036
Liu WLi YChen XHe J(2020)Maximum likelihood-based influence maximization in social networksApplied Intelligence10.1007/s10489-020-01747-8Online publication date: 10-Jun-2020
https://doi.org/10.1007/s10489-020-01747-8
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten