Motivated by online social networks that are linked together through overlapping users, we study the influence maximization problem on a multiplex, with each layer endowed with its own model of influence diffusion. This problem is a novel version of the influence maximization problem that necessitates new analysis incorporating the type of propagation on each layer of the multiplex. We identify a new property, generalized deterministic submodular, which when satisfied by the propagation in each layer, ensures that the propagation on the multiplex overall is submodular – for this case, we formulate ISF, the greedy algorithm with approximation ratio (1 − 1/e). Since the size of a multiplex comprising multiple OSNs may encompass billions of users, we formulate an algorithm KSN that runs on each layer of the multiplex in parallel. KSN takes an alpha-approximation algorithm A for the influence maximization problem on a single network as input, and has approximation ratio (1−epsilon)alpha/((o+1)k) for arbitrary epsilon > 0, o is the number of overlapping users, and k is the number of layers in the multiplex. Experiments on real and synthesized multiplexes validate the efficacy of the proposed algorithms for the problem of influence maximization in the heterogeneous multiplex.
Provided source code for ISF and KSN to approximate the MIM problem. KSN is implemented utilizing the IMM algorithm for algorithm A and is parallelized by layer of the multiplex.
Simply type make in the root directory of the source code
to compile mim. To create ER multiplexes for testing,
compile synth using command make synth.
mult.
mim takes as input a directory containing a multiplex in the following format:
Layers of the multiplex are indexed 0,...,k-1.
Each layer i of the multiplex has three files associated with it:
layeri
This file contains the directed graph representation for layer i
in plain text format. The first line must contain the number of nodes followed
by the number 1, so '10 1' for example.
The remainder of the file is weighted edge list format, where each line contains
(source node) (target node) (edge weight),
where the edge weight is an integer between 0 and 255. For the IC or LT models,
this weight is interpreted as the fractional weight (weight) / 255.
layerimodel
This file contains the influence propagation model of the layer, represented as
an integer. Currently supported values are 0 -- IC and 1 -- LT models.
layeriov
This file contains the overlapping information for this layer, in the following
format. On each line,
(node_id) (layer_id) (layer_node_id)
are specified, where node_id is the id of the vertex in this layer (i),
layer_id != i is the layer in which the this vertex also lies, and
layer_node_id is the id of the node in this other layer. For example,
if layer0ov contains the line
1 3 5,
it means that node 1 in layer 0 overlaps with node 5 in layer 3, and hence
if node 1 is activated in layer 0, node 5 is activated in layer 3.
To run KSN with 5 seeds and at most 10 threads on a multiplex in directory ./mult/: ./mim -M mult/ -k 5 -K -x 10 Same example except run single-threaded alg. ISF: ./mim -M mult/ -k 5 -I To create a synthetic multiplex with 5 ER layers, each with 100 nodes, edge prob 0.2, overlap fraction 0.1 (of 100) in directory ./mult: ./synth 100 0.2 5 0.1 mult/
mim outputs the seed set chosen, and expected activation of that set as computed
by 10000 Monte Carlo iterations.
synth outputs multiplex files in the directory specified
-M [multiplex dir]
-I (run ISF)
-K (run KSN)
-k [number of seeds]
-x [max number of threads (ISF always uses a single thread)]