A Heuristic for Influence Maximization Under Deterministic Linear Threshold Model
Abstract
Influence maximization (IM) is perhaps one of the most actively studied problems in network science. It is a combinatorial optimization problem in which, given a directed social network with influence weights, a spreading model, and a positive integer k, it is required to identify the set of seed nodes of size k which can make the largest influence in the network. We proposed an exact ILP model in our recent work and iterative solution approach to solve the IM problem under the so-called deterministic linear threshold spreading model. Since the solution describes how the diffusion happens for different time constraints, it is of interest to investigate how the various characteristics of the underlying graph relates to the result. In this paper, we present two new centrality metrics, computed from the input network structure, and use them to minimize the number of possible seed nodes. The solver chooses among the potential seed nodes and solves the problem, reducing the solution time. Benchmarking results are shown and discussed to demonstrate the efficiency of the proposed method.
Full Text:
PDFReferences
D. Acemoglu, A. Ozdaglar, and E. Yildiz. Diffusion
of innovations in social networks. In 50th IEEE Conference
on Decision and Control and European Control
Conference, pages 2329–2334, 2011. https:
//doi.org/10.1109/cdc.2011.6160999
F. Altarelli, A. Braunstein, L. Dall’Asta, and
R. Zecchina. Optimizing spread dynamics on graphs
by message passing. Journal of Statistical Mechanics:
Theory and Experiment, page P09011,
https://doi.org/10.1088/1742-5468/
/09/p09011
P. Bonacich. Factoring and weighting approaches to
status scores and clique identification. The Journal of
Mathematical Sociology, 2:113–120, 1972. https:
//doi.org/10.1080/0022250x.1972.9989806
S. Brin and L. Page. The anatomy of a large-scale
hypertextual web search engine. Computer Networks
and ISDN Systems, 30:107–117, 1998. https://
doi.org/10.1016/s0169-7552(98)00110-x
E. Csókás and T. Vinkó. An exact method for influence
maximization based on deterministic linear
threshold model. Central European Journal of Operations
Research, 31:269–286, 2023. https://doi.
org/10.1007/s10100-022-00807-3
K. Das, S. Samanta, and M. Pal. Study on centrality
measures in social networks: a survey. Social Network
Analysis and Mining, 8, 2018. https://doi.org/
1007/s13278-018-0493-2
R. Fourer, D.M. Gay, and B.W. Kernighan. AMPL.
A modeling language for mathematical programming.
Thomson, 1993. https://doi.org/10.
/978-3-642-83724-1_12
L. C. Freeman. A set of measures of centrality
based on betweenness. Sociometry, 40:35–41, 1977.
https://doi.org/10.2307/3033543
J. Goldenberg, B. Libai, and E. Muller. Talk of
the network: A complex systems look at the underlying
process of word-of-mouth. Marketing Letters,
(3):211–223, 2001. https://doi.org/10.
/a:1011122126881
M. Granovetter. Threshold models of collective behavior.
American Journal of Sociology, 83:1420–
, 1978. https://doi.org/10.1086/226707
F. Gursoy and D. Gunnec. Influence maximization
in social networks under deterministic linear threshold
model. Knowledge-Based Systems, 161:111–123,
https://doi.org/10.1016/j.knosys.
07.040
P.D. Karampourniotis, B.K. Szymanski, and G. Korniss.
Influence maximization for fixed heterogeneous
thresholds. Scientific Reports, 9:5573, 2019. https:
//doi.org/10.1038/s41598-019-41822-w
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, pages 137–146, 2003. https://doi.org/
1145/956750.956769
S. Kochemazov. Comparative study of combinatorial
algorithms for solving the influence maximization
problem in networks under a deterministic
linear threshold model. Procedia Computer Science,
:190–199, 2018. 7th International Young
Scientists Conference on Computational Science,
YSC2018. https://doi.org/10.1016/j.procs.
08.252
A. Lancichinetti, S. Fortunato, and F. Radicchi.
Benchmark graphs for testing community detection
algorithms. Phys. Rev. E, 78:046110, 2008. https:
//doi.org/10.1103/physreve.78.046110
B. Liu, G. Cong, D. Xu, and Y. Zeng. Time constrained
influence maximization in social networks.
In 2012 IEEE 12th International Conference on Data
Mining, pages 439–448, 2012. https://doi.org/
1109/icdm.2012.158
Z. Lu, W. Zhang, W. Wu, B. Fu, and D. Du. Approximation
and inapproximation for the influence maximization
problem in social networks under deterministic
linear threshold model. In 2011 31st International
Conference on Distributed Computing Systems Workshops, pages 160–165, 2011. https://doi.
org/10.1109/icdcsw.2011.33
Z. Lu, W. Zhang, W. Wu, and J. Kim. The complexity
of influence maximization problem in the deterministic
linear threshold model. Journal of Combinatorial
Optimization, 24:374–378, 2012. https:
//doi.org/10.1007/s10878-011-9393-3
Z. Lu, W. Zhang, W. Wu, J. Kim, and B. Fu. The complexity
of influence maximization problem in the deterministic
linear threshold model. Journal of Combinatorial
Optimization, 24(3):374–378, 2012. https:
//doi.org/10.1007/s10878-011-9393-3
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase,
E. Slooten, and S. M. Dawson. The bottlenose dolphin
community of doubtful sound features a large proportion
of long-lasting associations. Behavioral Ecology
and Sociobiology, 54(4):396–405, 2003. https:
//doi.org/10.1007/s00265-003-0651-y
M. E. J. Newman. Finding community structure in
networks using the eigenvectors of matrices. Physical
review E, 74(3):036104, 2006. https://doi.org/
1103/physreve.74.036104
K. Rahimkhani, A. Aleahmad, Ma. Rahgozar, and
A. Moeini. A fast algorithm for finding most
influential people based on the linear threshold
model. Expert Systems with Applications, 42:1353–
, 2015. https://doi.org/10.1016/j.eswa.
09.037
R. A. Rossi and N. K. Ahmed. The network data
repository with interactive graph analytics and visualization.
In AAAI, 2015. https://doi.org/10.
/aaai.v29i1.9277
R. A. Rossi, D. F. Gleich, A. H. Gebremedhin, and
M. A. Patwary. What if clique were fast? maximum
cliques in information networks and strong
components in temporal networks. arXiv preprint
arXiv:1210.5802, pages 1–11, 2012. https://doi.
org/10.48550/arXiv.1210.5802
R. A. Rossi, D. F. Gleich, A. H. Gebremedhin, and
M. A. Patwary. Fast maximum clique algorithms for
large graphs. In Proceedings of the 23rd International
Conference on World Wide Web (WWW), 2014.
https://doi.org/10.1145/2567948.2577283
G. Sabidussi. The centrality index of a graph. Psychometrika,
(4):581–603, 1966. https://doi.
org/10.1007/bf02289527
S. Segarra and A. Ribeiro. Stability and continuity of
centrality measures in weighted graphs. IEEE Transactions
on Signal Processing, 64:543–555, 2016.
https://doi.org/10.1109/tsp.2015.2486740
M. E. Shaw. Group structure and the behavior of individuals
in small groups. The Journal of Psychology,
:139–149, 1954. https://doi.org/10.1080/
1954.9712925
A. Singh, R. Singh, and S. Iyengar. Nodeweighted
centrality: a new way of centrality hybridization.
Computational Social Networks, 7:Article
nr. 6, 2020. https://doi.org/10.1186/
s40649-020-00081-w
N. Rama Suri and Y. Narahari. Determining the top-k
nodes in social networks using the Shapley value. In
Proceedings of the 7th international joint conference
on Autonomous agents and multiagent systems - Volume
, pages 1509–1512, 2008. https://dl.acm.
org/doi/10.5555/1402821.1402911
R. Xu. An Lp norm relaxation approach to positive
influence maximization in social network under
the deterministic linear threshold model. In Algorithms
and Models for the Web Graph, pages 144–
Springer, 2013. https://doi.org/10.1007/
-3-319-03536-9_12
DOI: https://doi.org/10.31449/inf.v48i4.4805
This work is licensed under a Creative Commons Attribution 3.0 License.