We consider the problem of selecting the most influential members within a social network, in order to disseminate a message as widely as possible. This problem, also referred to as seed selection for influence maximization, has been under intensive investigation since the emergence of social networks. Nonetheless, a large body of existing research is based on the assumption that the network is completely known, whereas little work considers partially observable networks. Yet, due to many issues including the extremely large size of current networks and privacy considerations, assuming full knowledge of the network is rather unrealistic. Despite this, an influencer often wishes to distribute its message far beyond the boundaries of the known network. In this preliminary study, we propose a set of novel heuristic algorithms that specifically target nodes at this boundary, in order to maximize influence across the whole network. We show that these algorithms outperform the state of the art by up to 38% in networks with partial observability.
Today’s vast online social networks connect people across geographical, cultural and
organizational boundaries. This offers a tremendous opportunity for quickly
disseminating a message to a global audience with only a limited budget. This could be
exploited for product marketing, but also for quickly mobilizing large crowds to help
during humanitarian crises [
How to choose such key individuals within a large network has been widely studied
in the computer science literature and is typically referred to as influence
maximization (IM) [
Although IM has attracted a great deal of attention in the past few years, the majority of existing work focuses on known networks, rather than the real-world situation where the full network is not known. In essence, little work considers partially observable networks, where only part of a network is visible to the decision maker. This is especially relevant, for instance, when an organization may be aware of its own members’ network links, but has little information about the wider network.
In this paper, we take the first steps towards addressing this problem. Specifically, we survey the state of the art and propose a new model for IM in partially observable networks. Furthermore, we propose a number of heuristic algorithms that target nodes at the boundary of the known network and, through an empirical evaluation on a realworld network, we show that these can outperform the current state of the art by up to 38% in settings with very limited observability. 2
In the following we first introduce the general influence maximization problem in fully observable settings and then we detail work that has looked at partially observable settings.
In the influence maximization problem, a (fully observable) network is specified along
with an activation function that describes the spread of influence. Initially, no
individuals in this network are activated, i.e., influenced by the message. Given this, the decision
maker picks a fixed number of individuals as seeds. These become activated and spread
the message, i.e., activate their neighbors, according to the specified activation function.
The aim of the decision maker is to maximize the total number of activated individuals
[
While solving this problem is NP-hard in general, there are several computationally
efficient approximate solutions with performance guarantees [
This work focuses on partially observable networks, and hence we avoid a detailed discussion of the state-of-the-art IM schemes for fully observable networks. Nonetheless, we describe the state-of-the-art IM algorithms we use in our numerical analysis.
Currently, the most successful IM algorithms with theoretical performance
guarantees [
graph obtained by removing each edge e in G with probability 1 p(e). The reverse reachable (RR) set for v in g is the set of nodes in g that can reach v. That is, for each node u in the RR set, there is a directed path from u to v in g.
Theoretically, it can be shown that if an RR set generated for v overlaps with a node set S with probability , then when we use S as the seed set to run an influence propagation process on G, v will be activated with probability .
These algorithms first determine how many RR sets need to be generated to provide statistical guarantees for the IM problem. Choosing too many RR sets increases the computational complexity, while choosing too few RR sets affects the algorithm’s performance guarantees. TIM/TIM+ predetermine the required number of RR sets and then generate them, while IMM produces RR sets one after another until a certain stopping condition is satisfied. Once the RR sets are generated, a greedy heuristic for the max-cover problem derived from these RR sets is applied to select the seeds, which is guaranteed to at least be within a factor (1 1e ) of the optimal case.
Influence maximization under uncertainty corresponds to a general class of problems,
where given limited network information and a fixed budget, the desire is to allocate the
budget to a set of seeds, so that the spread of influence is maximized. In particular, the
probability of influence among each pair of nodes and/or the network structure might be
(partially) unknown. This problem has been investigated in the literature in two general
settings:
One shot: Here, seed selection is performed only once given the available
information. For example, robust influence maximization [
Repeated: Here, seeds are selected incrementally, so that sampling/learning approaches
can be used to acquire information about the a priori unknown propagation
characteristics. These work can be classified into two sub-groups:
– Bandit-based approaches: In [
In this work, we explore influence maximization under a type of uncertainty which has not been investigated so far. In our setting, a part (or some parts) of a network is known (e.g., individuals that belong to the decision maker’s organization), while the rest is completely unobservable. We investigate the applicability of the state-of-the-art approaches, and propose new heuristic algorithms for seed selection. 3
We consider a dense network modeled by a directed graph G(V; E ; w) and called an influence network: – V = f1; 2; : : : ; N g indicates the set of nodes. Each node represents a network entity, for instance an individual. G represents a social network; – E V V is the set of directed edges; – w : E ! [0; 1] is a weight function, where w(i; j) is the likelihood (possibility) of j being influenced by i. Alternatively and with a slight change of notation, w can be defined as the weight matrix.
In an influence network, initially a seed set S V becomes activated. Every activated
node causes its neighbors to become (and stay) activated according to the independent
cascade model [
It should be mentioned that in addition to the independent- and weighted cascade models, the spread of influence through a network can be described by some other models, one of them being the well-known linear threshold model. In this work, however, we confine our attention to the cascade influence propagation model.
Departing from existing models in the literature, we assume that the network is only partially observable. Specifically, we assume that the decision maker, who selects the seeds, observes only one part of the network, denoted by G0 = (V0; E 0; w0). Naturally we have V0 V, E 0 E ( V0 V0), and w0 : E 0 ! [0; 1]. Note that the range of function w0 includes the weights of the edges belonging to E 0.
One specific case of partially observable networks is the organization-partitioned model of network. In such networks, a subset of nodes, O V, reveal their neighbors (and possibly the relevant edge-weights) to the decision makers, e.g., because they are members of the decision maker’s organization. We denote this subset of nodes as fully observable nodes, while the neighbors of nodes in O (that are not also in O) are denoted as boundary nodes. We assume only nodes in O can be selected as initial seeds. Figure 1 provides an illustrative example of an organization-partitioned network.
Concluding this section, we define the general problem of influence maximization in partially observable networks as follows: Given a specific activation function, a seed set size M and the observable part G0 of a network G, it is desired to find a seed set S V0 (with jSj M ), so that in the underlying network G, the total number of activated nodes through seeding S is maximized.
2 5 3 4 1 6 9 7 8 Fig. 1. Illustrative example of an organization-partitioned network, which is a spacial case of partially observable networks. The light nodes are observable. Note that there is only a weak tie between the observable and unobservable parts of the networks, which makes the influence maximization, and thereby the seed selection, particularly challenging.
In this paper, we confine our attention to heuristic-based IM (described in the following section), and leave the investigation of inference-based IM in partially observable network (where the unseen part of the network is reconstructed using generative models) for our future work. 3.1
Here the structure of the problem is such that reliable inference is not possible. This
might arise, for instance, due to restricted availability of samples or limited
computational capacity. In such circumstances, instead of inference, we explore simple rules for
selecting seed nodes:
– Random Selection: In this case, we select the seeds simply at random.
– Random with Neighbor Activation: Here, we first select the seeds at random, and
then for each seed, we activate one of its neighbors. This approach is based on the
friendship paradox [
Generative network model
Influence Maximisation
Algorithm
Network generation algorithm
Spread model
Spread algorithm
Filter Filtered network Inferred network(s)
Selected seed nodes
Message spread – Selection based on (Weighted) Degree: In this heuristic, we first rank the nodes in the known part of the network based on their degree, so that nodes with larger number of neighbors have higher ranks. Then we select node with highest rank as seeds.
Here we use the intuition that nodes with larger number of connections are very
likely to be highly influential. In the settings we considered in this paper,
neighbours typically had non-negligible influence on each other. However, in some
realworld social networks, users may have large numbers of followers but actually exert
little influence on them [
In the weighted version of this approach, we still rank the nodes based on their degree; however, in order to improve the influence probability in the unknown part of the network, we attach a higher weight for neighbours that are in the boundary set. For example, when w = 3, then node 6 in Figure 1 would have a weighted degree of 4, while node 7 would only have a weighted degree of 3 (since all its neighbours are fully observable). – State of the Art with Limited Visibility: Here we simply use the IM algorithms which are originally developed for known networks, for instance TIM and IMM described in Section 2.1. In doing so, we intend to investigate the extent to which the state of the art is applicable to partially known networks. Similar to the activation based on degree, TIM and IMM can be used in the weighted version. In essence, we run the TIM and IMM in the known part of the network as conventional; however, for selecting the RR sets, we weight the edges with connections to outside the boundary, although such connections are not completely visible to us. 4
In order to evaluate influence maximization algorithms in partially observable networks, we implemented a comprehensive benchmarking framework, as shown in Figure 2 (here, dashed lines indicate the use of a probabilistic model, and solid lines indicate data flow). Briefly, the figure shows how a full network is generated, then filtered to a partially observable network. The IM algorithm then selects seed nodes (potentially using inference) and the outcome is simulated. We implemented a range of algorithms for generating synthetic networks and filtering these. However, due to the limited space, we only report on a subset of our results. In the following, we first describe our experimental setup and then outline the results. 4.1
We use the NetHept5 dataset, a network of 15k nodes and 31k edges (representing
citations within the high energy physics theory community). We choose this because it
constitutes a real-world dataset of reasonable size and because it has been widely used
to benchmark influence maximization algorithms [
Throughout our experiments, we will generate partially observable networks with varying numbers of fully observable nodes (i.e., nodes that are observable and whose neighbours are also observable — see Section 3). We do this by initialising the set of fully observable nodes (O) to contain a number of seed nodes, chosen uniformly at random. In our experiment, we initially choose 4 seed nodes, but our results are similar for other settings. Then, we iteratively add one additional node to O at a time, either by picking a node from O and then adding one of its neighbours that is currently not in O to O (both uniformly at random), or, when no such neighbours exist, by adding a random node to O. This continues until O contains a target number of nodes.
Again, due to space reasons, we focus on the weighted cascade model (see Section 3), although we have observed broadly similar trends more generally in the independent cascade model (for various edge weight distributions).
We evaluate most of the heuristics described in Section 3.1. Here, we use Random
and Random Neighbour to denote Random Selection (without or with Neighbour
Activation). Weighted(1) represents selection based on degree, while Weighted(w) is the
weighted version that attaches a relative weight w to boundary nodes. Finally, IMM(1)
is the state-of-the-art IMM algorithm described in Section 2, and IMM(w) similarly
represents the weighted version. We choose IMM here, due to its consistently high
performance compared to other state-of-the-art algorithms [
To evaluate each influence maximization algorithm, we generate a partially observable network, run the algorithm on it and then simulate the influence spread on the chosen set of seeds 1,000 times to obtain an average spread. We repeat this process 1,000 times (to evaluate a wide range of partially observable networks) and present 5 This can be downloaded at https://www.microsoft.com/en-us/research/ wp-content/uploads/2016/02/weic-graphdata.zip. the overall average spread. The 95% confidence intervals are typically smaller than an absolute deviation of 2 from the average value, so are not plotted on the graphs. 4.2
180 160 140 d120 a e r p eS100 g a r e vA 80 60 40 20
IMM(1) IMM(2) IMM(5) Random RandomNeighbour Weighted(1) Weighted(2)
Weighted(5) 2% 4% 6% Network Visibility 8% 10%
Here, several interesting trends emerge. As expected, the state-of-the-art IMM algorithm performs will throughout all settings. However, looking more closely at cases with low observability (Figure 3), some of the heuristic approaches outperform it. Specifically, the degree-based heuristics perform consistently well, sometimes achieving an up to 19% higher average spread than IMM. For example, when 1% of nodes are fully observable, IMM achieves an average spread of 112:12 1:78 (with 95% confidence interval), while Weighted(2) achieves 133:19 1:95.6 This is likely because IMM focuses on maximising its influence only within the known part of the network. In settings with low visibility, this is a highly inaccurate view and the degree-based heuristics offer a better estimate of what nodes are influential across the full network. 6 A t-test confirms there is a statistically significant difference at the p < 0:0001 level. IMM(1) IMM(2) IMM(5) Random RandomNeighbour Weighted(1) Weighted(2) Weighted(5) 0 0% 20% 40% 60% Network Visibility 80% 100%
As visibility rises (also continuing in Figure 4), this difference becomes less pronounced, and by 10% visibility, they achieve a similar performance. As visibility rises further, IMM(1) eventually achieves the highest performance (from 50% visibility onwards). This is not surprising, since it is known to perform well in fully observable networks.
Looking specifically at the effect of adding higher weights for boundary nodes to the heuristics, this can lead to a significant increase in the average spread. However, the performance is sensitive to the exact parameter value, and for networks with higher visibility, a high weight can indeed lead to a decrease in performance, and is most pronounced for Weighted(5) in settings with 20–50% visibility. This is because the boundary nodes actually decrease in importance in the network as more of it is known to the algorithm.
Note that the relatively good performance of degree heuristics is surprising, as it
goes against the distinction between influential and high-degree nodes that has been
observed in some settings [
Promisingly, adding the weight to IMM significantly increases the average spread of IMM — up to 6% in some cases, and IMM(2) consistently performs better or as well as IMM across all settings. However, as for the degree-based heuristic, choosing a very large weight can lead to a decrease in performance for the same reasons as mentioned above.
Both random heuristics achieve a low level of performance, but using neighbour activation achieves a significantly higher spread than not using it (up to 100% more in some cases). This is potentially promising in settings where very little is known about the network, but where neighbours of known nodes can be activated. Note the apparent decrease in performance for larger networks is due to the way we filter nodes based on their neighbours — more connected nodes are likely to be included in our fully observable set earlier. Thus, when sampling a random node in a network with smaller visibility, it is more likely to be well connected, than when sampling from a network with full visibility.
40 35
IMM(1) IMM(2) IMM(5) Random RandomNeighbour Weighted(1) Weighted(2)
Weighted(5) 20 40 60 Number of Seeds 80 100
Finally, Figure 5 shows the average spread per initial seed chosen as the number of initial seeds is increased (in a setting with 1% visibility). This highlights that our heuristic techniques achieve the highest performance gains over the state of the art in settings with fewer initial seeds (a gain of up to 38% when there is just a single initial seed).
Overall, these are promising results, showing that in settings where large parts of the network are not observable and where only few seeds can be chosen, the state-ofthe-art algorithm does not necessarily perform best. Instead simple heuristics perform well, and both those heuristics and the current state of the art benefit from explicitly favouring nodes at the boundary of the known network. It should also be noted that the heuristics are several order of magnitude faster than IMM — a typical run of IMM took about 0.1–0.2 seconds, while the degree-based heuristics typically completed within 0.2–0.3ms. 5
In this paper, we presented initial results on influence maximization in partially observable networks. We showed that the current state of the art does not necessarily produce the best results, especially when only small parts of the network are visible. Indeed, we examined some settings where a degree-based heuristic leads to a 38% improvement over the state of the art.
In future work, we will examine these settings in more detail, to derive more principled inference-based algorithms that work well in a range of settings and that offer some performance guarantees.
We will look at influence maximization over different types of real-world networks to understand whether the relative performance of our simple heuristic depends on any parameters of the underlying network (e.g., degree assortativity).
We will then consider the case where the decision maker has access to a generative network model that can be used for inference about the structure of the unseen part of the network (conditional on the observed part) before application of IM algorithms. Two specific examples of such generative models include: – Sampling: An inference model is used to sample multiple snapshots of the unseen network. Across all snapshots, the average marginal influence of all nodes in V0 is calculated and a greedy IM approach is applied. – Maximum Likelihood: The model is used to calculate a single maximum likelihood network and an existing IM approach is applied to this.
Finally, we will investigate repeated settings, as described in Section 2.2, where seeds are selected incrementally and where information about the unknown part of the network is gradually revealed.
This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W911NF-16-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copy-right notation hereon. The work of S. M. was supported by a post-doctoral fellowship from the German Research Foundation (DFG) under Grant Number MA 7111/1-1.