Introduction

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 [15], for collecting data through participatory sensing [23] or for supporting machine intelligence through human computation and crowdsourcing [20]. However, tapping into this vast distributed processing and information resource requires organizations to effectively disseminate a message (e.g., a call for action or participation) far beyond their usual domain of direct influence (e.g., their existing customers or social media followers). This can be achieved by asking key individuals to spread the message to contacts within their respective social networks, ideally creating far-reaching cascades of repeated messages.

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) [7,12,10,3]. This body of work provides models that allow the prediction of network spread, given a fully known network, enabling those who wish to have their messages reach the most people, e.g., advertisers, marketers or public health professionals, to choose the best few people to target with their initial messaging.

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.

Related Work

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.

IM in Fully Observable Networks

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 [10].

While solving this problem is NP-hard in general, there are several computationally efficient approximate solutions with performance guarantees [10,14,6,21,3]. Some of these scale to realistic-sized networks with millions of nodes or more.

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 [1] are TIM and TIM+ [19], and IMM [18]. These algorithms are based on the concept of reverse reachable sets [3], defined below.

Definition 1 (Reverse Reachable Set). Let v be a node in some graph G, and g be a 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 − 1 e ) of the optimal case.

IM in Partially Observable Networks

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 [5] addresses uncertainty in the edge influence probability, which is represented as an interval in which the true probability may lie. Its goal is to maximize the worst-case ratio between the influence spread of the chosen seeds and the optimal set of seeds.

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 [16], a combinatorial bandit approach is used to model IM, where the agent selects a set of nodes as seeds at every round, and incurs a regret due to not selecting the optimal set. Existing regret-minimizing algorithms are used to solve the problem. In another bandit-based IM method [11], the seed selection scheme has two phases: (i) Exploration using a conventional influence maximization algorithm and (ii) Exploitation using a bandit algorithm. In influence maximization with semi-bandit feedback [22], upon activating the seeds, the learner only observes the influenced part of the network and uses an algorithm based on the well-known UCB strategy to select seeds. This latter algorithm can also accommodate a combinatorial bandit setting, since at every round a set of nodes can be selected.

-Other approaches: [9] learn the diffusion probability in an information-cascade model by likelihood maximization, and develop an expectation maximization seed selection algorithm. [17] investigates a scenario in which seed selection is performed under partial feedback, where at every round the result of past action(s) is not completely revealed. This creates a trade-off between delay (waiting time to see a desired partial outcome) and efficiency of seed selection in terms of spread of influence. This is somewhat similar to the trade-off in influence maximization in changing networks [24], which is between recency and accuracy of network information and efficiency of spread. Finally, [13] proposes a heuristic algorithm which at every round probes a set of nodes which have a high probability of large degrees. All probed nodes are ranked based on their degree, and nodes with the highest ranks are selected as seeds.

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.

Model and Problem

We consider a dense network modeled by a directed graph G(V, E, w) and called an influence network:

-V = {1, 2, . . . , N } 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 [8]. In this model, an activated node i ∈ V might activate each neighbor j with probability w(i, j). In a weighted cascade model, we have w(i, j)

= 1 |{(k,j)∈E}| , where |{(k, j) ∈ E}| is the in-degree of j.

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 G = (V , E , w ). Naturally we have V ⊆ V, E ⊆ E(⊆ V × V ), and w : E → [0, 1]. Note that the range of function w includes the weights of the edges belonging to E .

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 G of a network G, it is desired to find a seed set S ⊆ V (with |S| ≤ M ), so that in the underlying network G, the total number of activated nodes through seeding S is maximized. 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.

Heuristic-based Influence Maximization

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 [25], first discovered by S. L. Feld. It states that on an average basis, most people have fewer friends than their friends have. Thus, if we select some seed at random, it is beneficial to activate one of its neighbors, instead of the original node itself, due to possible larger number of connections. 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 [4]. Here, links could be pruned based on historical influence interactions, but we leave this to future work.

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.

Experimental Evaluation

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.

Experimental Setup

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 [18].

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 [1]. We leave the evaluation of centrality-based heuristics and other state-of-the-art approaches in partially observable settings to future work.

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 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.

Results

Figures 3 and 4 show the average spread of all algorithms in a setting with five seed nodes, as we vary the network visibility, i.e., the proportion of fully observable nodes (|O| / |V|). Figure 3 focuses on networks with particularly low observability (up to 10%), while Figure 4 shows the full range of proportions. 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. 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 [4]. This may be due to the fact that NetHept, as a citation network, has high-degree assortativity [2, Chapter 7], meaning that higher degree nodes are likely to be connected to other high-degree nodes and vice versa. This would mean that targeting a high-degree node can lead to influence spread via its high-degree neighbors (including within the unseen part of the network).

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. 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.

Conclusions and Future Work

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 V 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.