2018/02/05 by Alan Kuhnle, Kuhnle, Alan, Md Abdul Alim +7 · 1 citation
Computer Science · Physics and Astronomy · #Caching and Content Delivery #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Internet Traffic Analysis and Secure E-voting #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1802.01729
openalex publication_date 2018/02/05 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
Motivated by online social networks that are linked together through\noverlapping users, we study the influence maximization problem on a multiplex,\nwith each layer endowed with its own model of influence diffusion. This problem\nis a novel version of the influence maximization problem that necessitates new\nanalysis incorporating the type of propagation on each layer of the multiplex.\nWe identify a new property, generalized deterministic submodular, which when\nsatisfied by the propagation in each layer, ensures that the propagation on the\nmultiplex overall is submodular -- for this case, we formulate ISF, the greedy\nalgorithm with approximation ratio (1 - 1/e). Since the size of a multiplex\ncomprising multiple OSNs may encompass billions of users, we formulate an\nalgorithm KSN that runs on each layer of the multiplex in parallel. KSN takes\nan \α-approximation algorithm A for the influence maximization problem on\na single-layer network as input, and has approximation ratio\n\((1-\ε)\α)/((o+1)k) for arbitrary \ε > 0, o is the\nnumber of overlapping users, and k is the number of layers in the multiplex.\nExperiments on real and synthesized multiplexes validate the efficacy of the\nproposed algorithms for the problem of influence maximization in the\nheterogeneous multiplex. Implementations of ISF and KSN are available at\nhttp://www.alankuhnle.com/papers/mim/mim.html.\n