# Targeted Influential Nodes Selection in Location-Aware Social Networks

Authors: Susu Yang; Hui Li; Zhongyuan Jiang
Journal: Complexity
 (2018)

---

## Abstract

Given a target area and a location-aware social network, the location-aware influence maximization problem aims to find a set of seed users such that the information spread from these users will reach the most users within the target area. We show that the problem is NP-hard and present an approximate algorithm framework, namely, TarIM-SF, which leverages on a popular sampling method as well as spatial filtering model working on arbitrary polygons. Besides, for the large-scale network we also present a coarsening strategy to further improve the efficiency. We theoretically show that our approximate algorithm can provide a guarantee on the seed quality. Experimental study over three real-world social networks verified the seed quality of our framework, and the coarsening-based algorithm can provide superior efficiency.


---

## Body

## 1. Introduction

In recent years, social networks have become prevalent platforms for the spread of product adoption, ideas, and news. Under this trend, influence maximization (IM) problem is becoming popular, which aims to seekk users (referred to asseeds) to maximize the number of influenced users (referred to asinfluence spread) in the network. Kempe et al. [1] proved that this problem is NP-hard and presented an (1-1/e)-approximate algorithm by greedily selecting k seed users which has the maximum marginal gain of influence spread. Motivated by their work, a vast amount of studies then focused on improving the effect of influence spread and the efficiency, such as the heuristic-based algorithm PMIA [2] and the sketch-based algorithm IMM [3].However, many real-world applications such as location-based word-of-mouth marketing recently have location-aware requirements in IM. In [4], Li et al. focused on a location-aware IM (LAIM)query, which aims to seek k users to maximize the expected influence in a query region. They assumed that the network and the location of users are given beforehand, where an index can be constructed offline, and the target region is submitted online as a query. However, such assumption may not be always satisfied as the network and IM request are given at the same time, which is exactly the scenario discussed in traditional IM works [2, 5, 6]. Besides, existing works in LAIM can only answer the problem towards simple regions such as a rectangle or a circle. However, locations of users are always complicatedly visualized and managed via maps, the atomic regions of which are not necessarily rectangles or circles. Instead, they always show up as various and complex polygons. Therefore, it is meaningful to find an efficient method to address the LAIM problem, by targeting at an arbitrary polygon region, from scratch. Below we provide a running example to elaborate this point.Example. A company wants to sell a new product in a city. It is obvious that people in this city are potential buyers. In order to propagate this product to the public, we need to find several individuals who are the most influential in the network, and hope that, through their propagation, as many people as possible could know this product and then further purchase it.In our paper, we present a novel algorithm framework, namely, TarIM-SF (Targeted Influence Maximization with Spatial Filtering), to deal with this problem. Given a location-aware social network and a target region, we firstly adopt a spatial filtering model (SFM) to identify the targeted users. Then we will utilize the elegant sampling approach in latest IM solutions [3] to find seed nodes. In order to further improve the efficiency, we have coarsened the social network. In all, our contributions in this work are as follows:(i)
We relax the target region in LAIM to arbitrary polygons, which is more practical in real applications.(ii)
Secondly, our model can address LAIM from scratch without any assumption for offline processing.(iii)
To the best of our knowledge, we are the first to prove the hardness of LAIM theoretically in detail, and for the large-scale and complex networks, we propose a coarsening-based model that can further improve the efficiency with guaranteed seed quality.Experiments on real-world datasets Gowalla, Tweets, and Weibo demonstrate that our framework could generate a seed set with theoretically guaranteed quality, which outperforms a series of baseline methods in terms of influence spread quality. Besides, the coarsening-based algorithm can provide superior efficiency.The rest of paper is organized as follows. Section2 lists the related studies. Section 3 gives the definition of LAIM with proving its hardness and presents some fundamental knowledge. Afterwards, we discuss the proposed algorithm framework in Section 4. Section 5 shows the theoretical guarantee of seed quality. Section 6 reports the experimental results and some discussion. In Section 7, we conclude the paper.


## 2. Related Works

Kempe et al. [1] first formulated the influence maximization problem and proved that it is NP-hard in general, but can be approximated with (1-1/e-ϵ) factor. They presented a greedy algorithm with a provable approximation guarantee to solve this problem. However, the greedy algorithm needs to perform the Monte Carlo simulation [7] to obtain the approximate ratio, which has a large time overhead. Furthermore, in order to improve the efficiency and the effect, there has been a large body of research works that can be divided into three types.Simulation-based methods accurately estimate influence by simulating the diffusion process repeatedly with a theoretical guarantee. Leskovec et al. [8] proposed a CELF method with the lazy-forward heuristic, which is originally designed to optimize submodular functions in [9], as well as [10–14].Heuristic-based methods are developed to avoid using Monte Carlo simulation at the expense of solution quality. For example, Chen et al. [2] proposed to use local directed acyclic graphs to approximate the influence regions of nodes, while [15] restricting the spread of influence into communities and [6] approximating the influence spread using linear systems.Sketch-based methods resolved the inefficiency of Monte Carlo simulations without loss of accurate guarantees. Borges et al. [16] presented a nearly optimal time algorithm for IM under IC model. This method relies onreverse simulations of the diffusion process and builds sketches to estimate the influence function efficiently. In subsequential works, techniques for bounding the sketches’ size are developed [3, 17–21] and [3, 18, 19] are the representative ones that exhibit higher efficiency in all sketch-based methods. Moreover, Liu et al. [22] construct a community-level influence analysis model, instead of focusing on individual-influence, while [23] defining the outer influence of a community and aiming to find the most influential communities, as well as [24] constructing an influential propagation model considering the temporal-interaction between users in the social network.Recently, more additional demands for IM problem emerged, such as considering the interests of users [25, 26], geographical factor, or some factors of time. Especially in order to meet the location-aware requirements in IM, Li et al. [4] proposed a method to solve location-aware IM, which works by seeking k users to maximize the expected influence spread of the query region. Wang et al. [27] considered the distance between two users and defined the distance-aware IM problem. They proposed a priority based algorithm with (1-1/e)-approximation ratio. The authors in [28] also studied the DAIM problem, considering the distance between the locations and the users. Zhu et al. [29] proposed Gaussian based and distance based mobility models, to derive the location-aware propagation probability in LBSN. Zhou et al. [30] take users’ historical mobility behaviour into account and study the IM problem under O2O model. Li et al. [31] aim to find several seed users to maximize geographic spanning regions (MGSR) in the query region, while Li et al. [32] assume that users have their location preference and solve the IM problem for the targeted users. Furthermore, some works focus on spatial-temporal IM problem [33, 34], which aims to find k best trajectories to be attached with an advertisement and maximizes the number of influenced users. Besides the location, the interests/topics of users are also taken into consideration in IM, and [35] proposed an algorithm that returns top-k topics related to the query of a user. Su et al. [36] take not only users’ interests but also their preference for locations into account, to find the targeted users, and then seek seeds to maximize the influence for targeted users.


## 3. Problem Statements and Preliminaries

### 3.1. Problem Definition

Definition 1 (LAIM).
Given a location-aware social networkG=(V,E) where each node v∈V is associated with a location (denoted as v.ϕ), a budget k, and a target region Q, the location-aware influence maximization (LAIM) aims to find k seed nodes (denoted as S) from V, such that the influence spread from S can reach the most number of nodes in Q.We show the hardness of LAIM problem underIndependence Cascade(IC) model, which is one of the most popular diffusion models [1]. Before that, we first define a problem called Subset Cover, which will be utilized in the following content.Definition 2 (subset cover).
There are an element setU={u1,u2,…,un}, a subset Uq={uq1,uq2,…,uqt} of U, and a collection of subsets S={S1,S2,…,Sm} of U, and we wish to know whether there exist k subsets in S, whose union is equal to Uq.Theorem 3.
The location-aware influence maximization problem is NP-hard for IC model.Proof.
From [1], we know that the influence maximization is NP-hard by reduction from Set Cover. Here we can prove that Subset Cover problem above is also NP-hard by reduction from Set Cover problem; the process is as follows.
ForS andU in Set Cover problem, we get a subset Uq={uq1,uq2,…,uqt} fromU, and we get a new set U′={u1,u2,…,un,un+1,un+2,…,un+t} by addingt different elements toU, while getting a new collection S′={S1′,S2′,…,Sm′} ofV correspondingS, where Si′=Si∪un+j∣ifuqj∈Si,∀j∈t. This process can be completed in polynomial time. When we find a solutionA for Set Cover problem, the corresponding subsets A′ in S′ can cover all nodes in U′; and if we find the solution of Subset Cover problem, Set Cover problem can also be solved. Based on this, we are able to construct a corresponding directed graph with (m+t) nodes like the proof in [1]: there are nodei corresponding to each Si inS, nodej corresponding to each element uqj in Uq, and a directed edge (i,j) with activity pij, where pij=1 if uqj∈Si; otherwise it is equal to 0. The Subset Cover problem is equivalent to deciding if there is a setA in this graph with σA≥(t+k), where σA denotes the influence spread of node setA. Initially, if we find a setA which makes σA≥(t+k), the Subset Cover problem will be solved, and if all k nodes corresponding to sets in solution of Subset Cover are activated, allt nodes corresponding to set Uq will be activated.


### 3.2. Sampling Technique

Borgs et al. [16] introduced a sampling method called RIS, which first constructs a suitable number of sketches from different target nodes reversing DFS (referred to as RR sets R) and then finds out k users as the seed nodes with the maximum coverage of R. The process of constructing RR sets is as follows.Firstly, given an edge-weighted graphG=(V,E), we denote g=(V,E,p) as the influence graph ofG, wherep is the propagation probability for edges between two user nodes. We delete every edgee inG with probability (1-pe). After that, we need to randomly choose one node inV and then construct a hypergraph and get the RR set for it.Definition 4 (RR set).
Letv be a node in V. A RR set for v is generated by firstly sampling a graph g′ from g and then taking the set of nodes in g′ that can reach v.For instance, from hypergraphs in Figure1, we can get the RR sets as follows: R1={Z1,6,4,0,2,5,9,8,…}, R2={Z2,12,4,7, 5,9,6,8,…}, R3={Z3,2,6,4,3,5,0,8,…}, R4=Z4,7,12,9,0,5,1,10,… ⋯. Through the construction of R, we can seek k nodes as seeds which have the maximum coverage of R.Figure 1
Several hypergraphs constructed fromg′ (dotted line represents there is a path from a node to another and the path passes through other nodes; real line represents a directed edge).


### 3.3. Coarsening Method

Definition 5 ([37] coarsened influence graph).
Given a social networkG=(V,E), let g=(V,E,p) be an influence graph and P=Cjj∈[τ] be a partition of  V, where each Cj is strongly connected (SC). Then, a coarsened influence graph obtained from g is defined as a vertex-weighted influence graph H=(W,F,q,w), where(1)W=Cj∣j∈τ,F=Cx,Cy∣Cx≠Cy,∃u,v∈E,u∈Cx,v∈Cy,qCxCy=1-∏u,v∈Eu∈Cx,v∈Cy1-puv,∀Cx,Cy∈F,wCj=Cj,∀Cj∈WThe mappingV→W is defined as π(v)=Cj such that v∈Cj. For a vertex set S, we let π(S)=π(v)∣v∈S and F=(π(u),π(v))∣π(u)≠π(v),(u,v)∈E). We follow the same coarsening process as [37]. Given an influence graph g, whose distribution is Dg, we first construct subgraphs G1=V1,E1,…Gr=(Vr,Er), which are random graphs sampled from Dg. In these subgraphs, we identify the vertex sets connected to each other in all subgraphs, so that we get a partition P=C1,C2,…,Cτ of g and corresponding H=(W,F,q,w) (see Figure 2).Figure 2
Two subgraphs ofg and the coarsened influence graphH.
(a)
Subgraph 1 (b)
Subgraph 2 (c)
Coarsened influence graph


### 3.4. Spatial Filtering Model

In order to figure out which nodes fall into regionQ, the most intuitive way is to compare the location of each node with the boundary of Q, which is costly when Q is complex or V is very large. Herein, we will adopt an efficient method for this task. Our method works by comparing the convex hull of nodes with Q and iteratively removing those nodes falling out of Q. Finally, we can end with a group of nodes whose convex hull is inside Q. In this manner, we avoid enumerating all nodes inV. Notably, for a point setT, we could useGraham Scan method [38] to seek its convex hull. Let T={v1.ϕ,…,vn.ϕ} be the nodes’ locations and (q1,…,qmq) be the boundary of Q as a point sequence. Then the process of finding target nodes in Q is shown in Algorithm 1.Algorithm 1:SFM (T,Q).
Input: A point set T={v1.ϕ,…,vn.ϕ}, a polygon Q=(q1,…,qmq); Output: The points of T within Q. 1:Initialize i=1, Ti=T, Ci′=∅, C0′=∅; 2:repeat 3:Compute the convex hull Ci of Ti and compare Ci with Q; 4:if ((q1,…,qmq) are all outside Ci )⋀(∀c∈Ci are in Q) then 5:return  {C1′,C2′,…,Ci-1′,Ti}. 6:else if ((q1,…,qmq) are all outside Ci)⋀(∀c∈Ci are outside Q)⋀(Ci∩Q=∅) then 7:return  ∅. 8:else then 9:continue; 10:end if 11:end if 12: Ci′={vi1.ϕ,…,vij.ϕ} is in Q, 1≤j≤i; 13: Ti+1=Ti-Ci,i=i+1; 14:until  Ti=∅. 15:return  {C1′,C2′,…,Ci-1′}.


## 3.1. Problem Definition

Definition 1 (LAIM).
Given a location-aware social networkG=(V,E) where each node v∈V is associated with a location (denoted as v.ϕ), a budget k, and a target region Q, the location-aware influence maximization (LAIM) aims to find k seed nodes (denoted as S) from V, such that the influence spread from S can reach the most number of nodes in Q.We show the hardness of LAIM problem underIndependence Cascade(IC) model, which is one of the most popular diffusion models [1]. Before that, we first define a problem called Subset Cover, which will be utilized in the following content.Definition 2 (subset cover).
There are an element setU={u1,u2,…,un}, a subset Uq={uq1,uq2,…,uqt} of U, and a collection of subsets S={S1,S2,…,Sm} of U, and we wish to know whether there exist k subsets in S, whose union is equal to Uq.Theorem 3.
The location-aware influence maximization problem is NP-hard for IC model.Proof.
From [1], we know that the influence maximization is NP-hard by reduction from Set Cover. Here we can prove that Subset Cover problem above is also NP-hard by reduction from Set Cover problem; the process is as follows.
ForS andU in Set Cover problem, we get a subset Uq={uq1,uq2,…,uqt} fromU, and we get a new set U′={u1,u2,…,un,un+1,un+2,…,un+t} by addingt different elements toU, while getting a new collection S′={S1′,S2′,…,Sm′} ofV correspondingS, where Si′=Si∪un+j∣ifuqj∈Si,∀j∈t. This process can be completed in polynomial time. When we find a solutionA for Set Cover problem, the corresponding subsets A′ in S′ can cover all nodes in U′; and if we find the solution of Subset Cover problem, Set Cover problem can also be solved. Based on this, we are able to construct a corresponding directed graph with (m+t) nodes like the proof in [1]: there are nodei corresponding to each Si inS, nodej corresponding to each element uqj in Uq, and a directed edge (i,j) with activity pij, where pij=1 if uqj∈Si; otherwise it is equal to 0. The Subset Cover problem is equivalent to deciding if there is a setA in this graph with σA≥(t+k), where σA denotes the influence spread of node setA. Initially, if we find a setA which makes σA≥(t+k), the Subset Cover problem will be solved, and if all k nodes corresponding to sets in solution of Subset Cover are activated, allt nodes corresponding to set Uq will be activated.


## 3.2. Sampling Technique

Borgs et al. [16] introduced a sampling method called RIS, which first constructs a suitable number of sketches from different target nodes reversing DFS (referred to as RR sets R) and then finds out k users as the seed nodes with the maximum coverage of R. The process of constructing RR sets is as follows.Firstly, given an edge-weighted graphG=(V,E), we denote g=(V,E,p) as the influence graph ofG, wherep is the propagation probability for edges between two user nodes. We delete every edgee inG with probability (1-pe). After that, we need to randomly choose one node inV and then construct a hypergraph and get the RR set for it.Definition 4 (RR set).
Letv be a node in V. A RR set for v is generated by firstly sampling a graph g′ from g and then taking the set of nodes in g′ that can reach v.For instance, from hypergraphs in Figure1, we can get the RR sets as follows: R1={Z1,6,4,0,2,5,9,8,…}, R2={Z2,12,4,7, 5,9,6,8,…}, R3={Z3,2,6,4,3,5,0,8,…}, R4=Z4,7,12,9,0,5,1,10,… ⋯. Through the construction of R, we can seek k nodes as seeds which have the maximum coverage of R.Figure 1
Several hypergraphs constructed fromg′ (dotted line represents there is a path from a node to another and the path passes through other nodes; real line represents a directed edge).


## 3.3. Coarsening Method

Definition 5 ([37] coarsened influence graph).
Given a social networkG=(V,E), let g=(V,E,p) be an influence graph and P=Cjj∈[τ] be a partition of  V, where each Cj is strongly connected (SC). Then, a coarsened influence graph obtained from g is defined as a vertex-weighted influence graph H=(W,F,q,w), where(1)W=Cj∣j∈τ,F=Cx,Cy∣Cx≠Cy,∃u,v∈E,u∈Cx,v∈Cy,qCxCy=1-∏u,v∈Eu∈Cx,v∈Cy1-puv,∀Cx,Cy∈F,wCj=Cj,∀Cj∈WThe mappingV→W is defined as π(v)=Cj such that v∈Cj. For a vertex set S, we let π(S)=π(v)∣v∈S and F=(π(u),π(v))∣π(u)≠π(v),(u,v)∈E). We follow the same coarsening process as [37]. Given an influence graph g, whose distribution is Dg, we first construct subgraphs G1=V1,E1,…Gr=(Vr,Er), which are random graphs sampled from Dg. In these subgraphs, we identify the vertex sets connected to each other in all subgraphs, so that we get a partition P=C1,C2,…,Cτ of g and corresponding H=(W,F,q,w) (see Figure 2).Figure 2
Two subgraphs ofg and the coarsened influence graphH.
(a)
Subgraph 1 (b)
Subgraph 2 (c)
Coarsened influence graph


## 3.4. Spatial Filtering Model

In order to figure out which nodes fall into regionQ, the most intuitive way is to compare the location of each node with the boundary of Q, which is costly when Q is complex or V is very large. Herein, we will adopt an efficient method for this task. Our method works by comparing the convex hull of nodes with Q and iteratively removing those nodes falling out of Q. Finally, we can end with a group of nodes whose convex hull is inside Q. In this manner, we avoid enumerating all nodes inV. Notably, for a point setT, we could useGraham Scan method [38] to seek its convex hull. Let T={v1.ϕ,…,vn.ϕ} be the nodes’ locations and (q1,…,qmq) be the boundary of Q as a point sequence. Then the process of finding target nodes in Q is shown in Algorithm 1.Algorithm 1:SFM (T,Q).
Input: A point set T={v1.ϕ,…,vn.ϕ}, a polygon Q=(q1,…,qmq); Output: The points of T within Q. 1:Initialize i=1, Ti=T, Ci′=∅, C0′=∅; 2:repeat 3:Compute the convex hull Ci of Ti and compare Ci with Q; 4:if ((q1,…,qmq) are all outside Ci )⋀(∀c∈Ci are in Q) then 5:return  {C1′,C2′,…,Ci-1′,Ti}. 6:else if ((q1,…,qmq) are all outside Ci)⋀(∀c∈Ci are outside Q)⋀(Ci∩Q=∅) then 7:return  ∅. 8:else then 9:continue; 10:end if 11:end if 12: Ci′={vi1.ϕ,…,vij.ϕ} is in Q, 1≤j≤i; 13: Ti+1=Ti-Ci,i=i+1; 14:until  Ti=∅. 15:return  {C1′,C2′,…,Ci-1′}.


## 4. TarIM-SF Framework

Here we describe our TarIM-SF framework in detail. In our LAIM problem, target users change from the whole network in classic IM problem into users in a target region. As the construction of RR sets starts from the target users, it is reasonable for us to construct enough RR setsR over the whole network for users in the target region within our problem and then choose the node set s which maximizes the coverage of R (referred to as FR(s)). Based on this idea, we first need to identify the users in the target region before constructing RR sets, which is addressed using the method proposed in Section 3.4. Moreover, in order to improve the efficiency of constructing RR sets, we have coarsened the network using the method proposed in Section 3.3. More details are given in Algorithm 2.Algorithm 2:TarIM-SF (G,Q,k,ϵ).
Input: A location-aware social network G=(V,E), a query polygon Q, and a budget k; Output: A seed set S. 1:Initialize S=∅, a set of goal users  qs=∅; 2: T← location points of V; 3: qs← SFM (T,Q); 4: G′← Coarsening (G), according to Algorithm 1 in [37]; 5: R← Sampling (G′,qs,k,ϵ), according to Algorithm 2 in [3]; 6: for  i=0 to k-1  do 7: s′← seek a node in G′ with the maximum marginal coverage for R; 8: s← choose a vertex in s′ randomly; 9: S←S∪{s}; 10:end for 11:return  S.For instance, in Figure3, given a location-aware social networkG, k=1, and a query region Q (such as a triangle), we first use SFM (line 3) to identify the goal users {3,4,6}, then we coarsen the whole network, and we get the partition P={C1,C2,C3,C4}, where C1=1,C2=4,6,7,C3=5,C4=2,3 (line 4). Next we will sample the coarsened influence graph and construct enough RR sets for the goal users (line 5). In the coarsened influence graph, the probability of partition node C4 being chosen to construct RR set is 1/3, and there is 2/3-probability for node C2. As a result, we get RR sets: R1={C2,C4}, R2={C4}, R3={C2,C4}. We can see that node C4 has the maximum coverage of R, including R1, R2, R3. In turn for the original network graph, we choose one user node randomly in C4 as the seed, such as node 2 (lines 6-10).Figure 3
An example.In our framework, the first step is to identify the users in the target regionQ, whose complexity depends on the location distribution of all nodes. In case that all users’ locations are uniformly randomly distributed, the time complexity for identifying users within the target region is O(n1/3mq) under our spatial filtering model, where n=V and mq is the number of points for Q. The second step is to coarsen the network, which requires OrV+E time, where r denotes the number of random subgraphs sampled from g. Afterwards, we use algorithm in [3] to seek solution in coarsened influence network, and the time of this step is spent on constructing RR sets for target region. The complexity of this process is O(∑j∈[R]w(Rj)), w(Rj) denoting the edges number of thei-th RR set, where R is decided by the parameters λ′ and λ∗ in [3], as well as the number of nodes and edges in the coarsened influence graph.


## 5. Effectiveness Study

We will subsequently conduct a theoretical study over the seed quality of our algorithm framework for both cases when coarsening is present or not.


### 5.1. Seed Quality without Coarsening

In [1], it has been proved that, under Independent Cascade model, the result influence function σ(·) is sunmodular. Here we define σ(·) as the target influence spread, which is the number of influenced nodes in target region. It is easy to see that, for any setsS andT, S⊆T, and any elements v, σ(S∪{v})-σ(S)≥σ(T∪{v})-σ(T)≥ also holds. Hence, the function σ(·) is submodular.Theorem 6 (see [1]).
For a nonnegative, monotone submodular functionf, let Sko be a size-k set by selecting one element at a time, each time choosing the element which has the maximum marginal function value. Assuming Sk∗ is the set that maximizes the value of f over all k-element sets, then f(Sko)≥(1-1/e)·f(Sk∗); in other words, Sko guarantees a (1-1/e)-approximation.So if we get a seed setSout by adopting a greedy algorithm, Sout is a (1-1/e)-approximate solution for the location-aware influence maximization problem. Then we will show the performance guarantee when we adopt IMM method [3] as the greedy approach.Lemma 7 (see [16]).
For any seed set S and any vertexv, the probability that a diffusion process from S can activate v equals the probability that S overlaps an RR set for v.We generate a sizeable setR of random RR sets for the nodes in target region Q, and for any seed setS, the fraction FR(S) of RR sets in R covered byS is the unbiased estimator of E(σ(S))/nq, where nq is the number of vertices in target region Q. In TIM+ [17], it has been proved that the solution which covers the maximum number of RR sets provides a (1-1/e-ϵ)-approximation with at least (1-1/nl) probability, but the number of RR sets is at least λ/OPT, whereOPT is the maximum expected influence of any size-k nodes set inG and λ is a function of k,l,n, and ϵ. In IMM, it seeks a tighter lower boundLB ofOPT than TIM+. Next, based on the analysis of the performance guarantee in the IMM, we will describe the parameter settings and performance guarantee in our framework.LetR1,R2,…,Rθ be the sequence of generated RR sets for nodes in the target region Q. Let Sk be any size-k seed set inG and xi be random variable that equals 0 if Sk∩Ri=∅ and 1 otherwise; then based on Lemma 7, we have(2)EσSk=nqθ·E∑i=1θxi.Consider Sk∗ is the size-k node set with the maximum expected influence; let OPT=E[σ(Sk∗)]. From (2), we can get that nq·FR(Sk∗) is an unbiased estimator ofOPT. By Corollary 2 in which we set p=OPT/nq and Lemma 3 in [3], we have the following.Lemma 8.
Letϵ1>0, δ1∈(0,1), and(3)θ1=2nq·log⁡1/δ1OPT·ϵ12,if θ≥θ1, then nq·FR(Sk∗)≥(1-ϵ1)·OPT holds with at least (1-δ1) probability.Assuming that our framework without coarsening returns a solutionSk′, and if nq·FR(Sk∗)≥(1-ϵ1)·OPT holds, according to the properties of the greedy approach, then(4)nq·FRSk′≥1-1e·nq·FRSk∗≥1-1e·1-ϵ1·OPTLemma 9.
Letϵ1<ϵ, δ2∈(0,1), and(5)θ2=2-2/e·nq·log⁡nk/δ2OPT·ϵ-1-1/e·ϵ12,if (4) holds and θ≥θ2, then E(σ(Sk′))≥(1-1/e-ϵ)·OPT holds with at least (1-δ2) probability.Based on Lemmas8 and 9, we have the following.Theorem 10.
Given anyϵ1≤ϵ and any δ1,δ2∈(0,1) with δ1+δ2≤1/nl, if θ≥max⁡{θ1,θ2}, the result which IMM returns is a (1-1/e-ϵ)-approximate solution with (1-1/nl) probability.For the parameters in Theorem10, we set δ1=δ2=1/(2nl), and under this setting, θ is minimized when θ1=θ2, and ϵ1=ϵ·α/1-1/e·α·β, where(6)α=llog⁡n+log⁡2,β=1-1e·log⁡nk+llog⁡n+log⁡2.In this case, θ=(2nq·1-1/e·α+β)2/OPT·ϵ2, and conversely if we set θ=λ∗/OPT, where(7)λ∗=2nq·1-1/e·α+β2ϵ2,the seed set Sk′ that covers the maximum number of RR sets is a (1-1/e-ϵ)-approximation. However, asOPTis unknown in advance, we will find a tight lower boundLB ofOPT as IMM method. In the sampling phase in IMM, Lemma 6, Lemma 7, and Lemma 8 in [3] proved that LB≤OPT andLB is close toOPT. And based on that, we can also prove that LB≤OPT andLB is a tight lower bound ofOPT with a high probability by changing n to nq.Theorem 11.
With at least(1-1/nl) probability, sampling algorithm in our framework returns a set R of RR sets with R≥λ∗/OPT, where λ∗ is as defined in (7).Combining Theorem10 and Theorem 11, our algorithm framework without coarsening can get a solution Sout which is a (1-1/e-ϵ)-approximation with a high probability.


### 5.2. Seed Quality for Coarsening Method

In this part, we will show the result seed setSout can achieve (1-1/e-ϵ)·αg-approximation, when coarsening technique is adopted to improve the efficiency. Based on the study in [37], for the target region Q, we will get the following equation:(8)infg⁡Q,S=∑E′⊆EpE′∣E·RV,E′Q,S,where pE′∣E=∏e∈E′pe·∏e∈E∖E′1-pe, Rg(Q,S) is the number (sum of weights) of vertices in Q that are reachable fromS in g, and infg⁡(Q,S) is the number of vertices in Q thatS can activate in g, which equals σ(S) in Section 5.1 and is submodular.In the coarsened influence graphH=(W,F,q,w), we also have(9)infH⁡Q,πS=∑Y⊆FqY∣F·RW,YQ,πS.It denotes the sum of weights for nodes in Q that π(S) can activate inH. After coarsening the network, we define I=(V,E,p′), where p′uv=1 if u,v∈Cj for all j∈[τ]; otherwise p′uv=puv, and infI⁡(Q,S) is the number of users in target region Q thatS can activate inI.Here, we show the relationship betweenH and g in terms of influence function throughI, which has the same structure as g.Lemma 12.
For anyQ and any S⊆V, infI⁡(Q,S)=infH⁡(Q,π(S)).Proof.
For anyu andv inV, “ucan reachv through the edges inE withp” if and only if “π(u) can reach π(v) through the edges inF withq”, since every subgraph (Cj,Ej), j⊆[τ], is strongly connected. Therefore, it holds that R(V,E)(Q,S)=R(W,Y)(Q,π(S)). Thus,(10)infI⁡Q,S=∑E′⊆Ep′E′∣E·RV,E′Q,S=∑Y⊆FqY∣F·RW,YQ,πS=infH⁡Q,πSForg andI, we also can find the relationship between them as follows.Lemma 13.
For anyQ and any S⊆V, infg⁡(Q,S)≤infI⁡(Q,S).Proof.
g andI are the influence graph with the same structure, but pe≤p′e for every edgee. So infg⁡(Q,S)≤infI⁡(Q,S) for any S⊆V.
For any subgraphgV′=(V′,E′) of g, V′⊆V, itsstrongly connected reliability, denoted as Rel(gV′), is defined the same as in Equation 14 in [37] and indicates the probability that gV′ is strongly connected.Lemma 14.
inf I ⁡ ( Q , S ) ≤ ∏ j ∈ τ R e l ( g [ C j ] ) - 1 · inf g ⁡ ( Q , S ), for any Q and S⊆V.Proof.
For eachj∈[τ], we define Ej=u,v∈E∣u,v∈Cj and E0=E∖(⋃j∈[τ]Ej). For Xj⊆Ej(j∈[τ]) and X0⊆E0, R(V,X0∪⋃jXj)(S)=R(V,X0∪⋃jEj)(S) holds if every subgraph (Cj,Xj) for j∈[τ] is strongly connected. Thus(11)infg⁡Q,S=∑X1⊆E1pX1∣E1⋯∑Xτ⊆EτpXτ∣Eτ∑X0⊆E0pX0∣E0·RV,X0∪⋃jXjS≥∑X1⊆E1C1,X1isSCpX1∣E1⋯∑Xτ⊆EτCτ,XτisSCpXτ∣Eτ∑X0⊆E0pX0∣E0·RV,X0∪⋃jXjS=∏j∈τRelgCj·infI⁡Q,STheorem 15.
For anyQ and any S⊆V, infg⁡(Q,S)≤infH⁡Q,πS≤∏j∈τRel(g[Cj])-1·infg⁡(Q,S).LetS∗ and T∗ be the optimal solutions of size k for g and H, respectively. Based on Lemma 12 and Lemma 13, we can sure that infHQ,T∗≥infg(Q,S∗), and have(12)infHQ,Sout≥1-1e-ϵ·infHQ,T∗≥1-1e-ϵ·infgQ,S∗Then applying Lemma14, we have(13)infHQ,Sout≥∏j∈τRelgCj·1-1e-ϵ·infgQ,S∗Therefore, our coarsening-based algorithm achieves a(1-1/e-ϵ)·αg-approximate solution for g, where αg refers to ∏j∈[τ]Rel(g[Cj]).


## 5.1. Seed Quality without Coarsening

In [1], it has been proved that, under Independent Cascade model, the result influence function σ(·) is sunmodular. Here we define σ(·) as the target influence spread, which is the number of influenced nodes in target region. It is easy to see that, for any setsS andT, S⊆T, and any elements v, σ(S∪{v})-σ(S)≥σ(T∪{v})-σ(T)≥ also holds. Hence, the function σ(·) is submodular.Theorem 6 (see [1]).
For a nonnegative, monotone submodular functionf, let Sko be a size-k set by selecting one element at a time, each time choosing the element which has the maximum marginal function value. Assuming Sk∗ is the set that maximizes the value of f over all k-element sets, then f(Sko)≥(1-1/e)·f(Sk∗); in other words, Sko guarantees a (1-1/e)-approximation.So if we get a seed setSout by adopting a greedy algorithm, Sout is a (1-1/e)-approximate solution for the location-aware influence maximization problem. Then we will show the performance guarantee when we adopt IMM method [3] as the greedy approach.Lemma 7 (see [16]).
For any seed set S and any vertexv, the probability that a diffusion process from S can activate v equals the probability that S overlaps an RR set for v.We generate a sizeable setR of random RR sets for the nodes in target region Q, and for any seed setS, the fraction FR(S) of RR sets in R covered byS is the unbiased estimator of E(σ(S))/nq, where nq is the number of vertices in target region Q. In TIM+ [17], it has been proved that the solution which covers the maximum number of RR sets provides a (1-1/e-ϵ)-approximation with at least (1-1/nl) probability, but the number of RR sets is at least λ/OPT, whereOPT is the maximum expected influence of any size-k nodes set inG and λ is a function of k,l,n, and ϵ. In IMM, it seeks a tighter lower boundLB ofOPT than TIM+. Next, based on the analysis of the performance guarantee in the IMM, we will describe the parameter settings and performance guarantee in our framework.LetR1,R2,…,Rθ be the sequence of generated RR sets for nodes in the target region Q. Let Sk be any size-k seed set inG and xi be random variable that equals 0 if Sk∩Ri=∅ and 1 otherwise; then based on Lemma 7, we have(2)EσSk=nqθ·E∑i=1θxi.Consider Sk∗ is the size-k node set with the maximum expected influence; let OPT=E[σ(Sk∗)]. From (2), we can get that nq·FR(Sk∗) is an unbiased estimator ofOPT. By Corollary 2 in which we set p=OPT/nq and Lemma 3 in [3], we have the following.Lemma 8.
Letϵ1>0, δ1∈(0,1), and(3)θ1=2nq·log⁡1/δ1OPT·ϵ12,if θ≥θ1, then nq·FR(Sk∗)≥(1-ϵ1)·OPT holds with at least (1-δ1) probability.Assuming that our framework without coarsening returns a solutionSk′, and if nq·FR(Sk∗)≥(1-ϵ1)·OPT holds, according to the properties of the greedy approach, then(4)nq·FRSk′≥1-1e·nq·FRSk∗≥1-1e·1-ϵ1·OPTLemma 9.
Letϵ1<ϵ, δ2∈(0,1), and(5)θ2=2-2/e·nq·log⁡nk/δ2OPT·ϵ-1-1/e·ϵ12,if (4) holds and θ≥θ2, then E(σ(Sk′))≥(1-1/e-ϵ)·OPT holds with at least (1-δ2) probability.Based on Lemmas8 and 9, we have the following.Theorem 10.
Given anyϵ1≤ϵ and any δ1,δ2∈(0,1) with δ1+δ2≤1/nl, if θ≥max⁡{θ1,θ2}, the result which IMM returns is a (1-1/e-ϵ)-approximate solution with (1-1/nl) probability.For the parameters in Theorem10, we set δ1=δ2=1/(2nl), and under this setting, θ is minimized when θ1=θ2, and ϵ1=ϵ·α/1-1/e·α·β, where(6)α=llog⁡n+log⁡2,β=1-1e·log⁡nk+llog⁡n+log⁡2.In this case, θ=(2nq·1-1/e·α+β)2/OPT·ϵ2, and conversely if we set θ=λ∗/OPT, where(7)λ∗=2nq·1-1/e·α+β2ϵ2,the seed set Sk′ that covers the maximum number of RR sets is a (1-1/e-ϵ)-approximation. However, asOPTis unknown in advance, we will find a tight lower boundLB ofOPT as IMM method. In the sampling phase in IMM, Lemma 6, Lemma 7, and Lemma 8 in [3] proved that LB≤OPT andLB is close toOPT. And based on that, we can also prove that LB≤OPT andLB is a tight lower bound ofOPT with a high probability by changing n to nq.Theorem 11.
With at least(1-1/nl) probability, sampling algorithm in our framework returns a set R of RR sets with R≥λ∗/OPT, where λ∗ is as defined in (7).Combining Theorem10 and Theorem 11, our algorithm framework without coarsening can get a solution Sout which is a (1-1/e-ϵ)-approximation with a high probability.


## 5.2. Seed Quality for Coarsening Method

In this part, we will show the result seed setSout can achieve (1-1/e-ϵ)·αg-approximation, when coarsening technique is adopted to improve the efficiency. Based on the study in [37], for the target region Q, we will get the following equation:(8)infg⁡Q,S=∑E′⊆EpE′∣E·RV,E′Q,S,where pE′∣E=∏e∈E′pe·∏e∈E∖E′1-pe, Rg(Q,S) is the number (sum of weights) of vertices in Q that are reachable fromS in g, and infg⁡(Q,S) is the number of vertices in Q thatS can activate in g, which equals σ(S) in Section 5.1 and is submodular.In the coarsened influence graphH=(W,F,q,w), we also have(9)infH⁡Q,πS=∑Y⊆FqY∣F·RW,YQ,πS.It denotes the sum of weights for nodes in Q that π(S) can activate inH. After coarsening the network, we define I=(V,E,p′), where p′uv=1 if u,v∈Cj for all j∈[τ]; otherwise p′uv=puv, and infI⁡(Q,S) is the number of users in target region Q thatS can activate inI.Here, we show the relationship betweenH and g in terms of influence function throughI, which has the same structure as g.Lemma 12.
For anyQ and any S⊆V, infI⁡(Q,S)=infH⁡(Q,π(S)).Proof.
For anyu andv inV, “ucan reachv through the edges inE withp” if and only if “π(u) can reach π(v) through the edges inF withq”, since every subgraph (Cj,Ej), j⊆[τ], is strongly connected. Therefore, it holds that R(V,E)(Q,S)=R(W,Y)(Q,π(S)). Thus,(10)infI⁡Q,S=∑E′⊆Ep′E′∣E·RV,E′Q,S=∑Y⊆FqY∣F·RW,YQ,πS=infH⁡Q,πSForg andI, we also can find the relationship between them as follows.Lemma 13.
For anyQ and any S⊆V, infg⁡(Q,S)≤infI⁡(Q,S).Proof.
g andI are the influence graph with the same structure, but pe≤p′e for every edgee. So infg⁡(Q,S)≤infI⁡(Q,S) for any S⊆V.
For any subgraphgV′=(V′,E′) of g, V′⊆V, itsstrongly connected reliability, denoted as Rel(gV′), is defined the same as in Equation 14 in [37] and indicates the probability that gV′ is strongly connected.Lemma 14.
inf I ⁡ ( Q , S ) ≤ ∏ j ∈ τ R e l ( g [ C j ] ) - 1 · inf g ⁡ ( Q , S ), for any Q and S⊆V.Proof.
For eachj∈[τ], we define Ej=u,v∈E∣u,v∈Cj and E0=E∖(⋃j∈[τ]Ej). For Xj⊆Ej(j∈[τ]) and X0⊆E0, R(V,X0∪⋃jXj)(S)=R(V,X0∪⋃jEj)(S) holds if every subgraph (Cj,Xj) for j∈[τ] is strongly connected. Thus(11)infg⁡Q,S=∑X1⊆E1pX1∣E1⋯∑Xτ⊆EτpXτ∣Eτ∑X0⊆E0pX0∣E0·RV,X0∪⋃jXjS≥∑X1⊆E1C1,X1isSCpX1∣E1⋯∑Xτ⊆EτCτ,XτisSCpXτ∣Eτ∑X0⊆E0pX0∣E0·RV,X0∪⋃jXjS=∏j∈τRelgCj·infI⁡Q,STheorem 15.
For anyQ and any S⊆V, infg⁡(Q,S)≤infH⁡Q,πS≤∏j∈τRel(g[Cj])-1·infg⁡(Q,S).LetS∗ and T∗ be the optimal solutions of size k for g and H, respectively. Based on Lemma 12 and Lemma 13, we can sure that infHQ,T∗≥infg(Q,S∗), and have(12)infHQ,Sout≥1-1e-ϵ·infHQ,T∗≥1-1e-ϵ·infgQ,S∗Then applying Lemma14, we have(13)infHQ,Sout≥∏j∈τRelgCj·1-1e-ϵ·infgQ,S∗Therefore, our coarsening-based algorithm achieves a(1-1/e-ϵ)·αg-approximate solution for g, where αg refers to ∏j∈[τ]Rel(g[Cj]).


## 6. Results and Discussion

In this section, we conduct experiments on several real-world datasets to test the performance of the proposed algorithm framework. All algorithms are implemented in C++ and run on Ubuntu 16.10 machine with Intel Core i5-6500 quad-core, 3.20GHz, 16GB RAM.In the following experiments, we use three location-aware social networks, namely, Gowalla, Tweets, and Weibo. The statistics for the datasets are listed in Table1 (n represents the number of vertices andm represents the number of edges). By default, we use a randomly selected Q for all datasets, and the number of user nodes falling in Q is denoted as nq. We conduct our experiments on WC model, which is widely used for information diffusion. For the weight of every edge, we set the probability of an edge (u,v) as 1/Nv, where Nv denotes the in-degree of user node v. In TarIM-SF, we set ϵ=0.1.Table 1
Datasets statistic.
Datasets n m Gowalla 196,585 351,452 Tweets 554,372 2,402,720 Weibo 1,020,730 16,490,916


### 6.1. Comparison with Baseline

We evaluate the performance of our algorithm frameworkTarIM-SF compared with methodAssembly in [4] under WC model. In order to estimate the performance in general, we selected three regions with fixed nq for each dataset (nq≈20K for Gowalla, nq≈120K for Tweets, and nq≈120K for Weibo) and reported the average performance, while varying k for Gowalla from 10 to 50 and k for Tweets and Weibo from 100 to 500. In Figure 4, we can see that the target influence spread of seeds in our framework is obviously superior to that ofAssembly, especially on Tweets and Gowalla.Figure 4
Influence spread under WC model.
(a)
Gowalla(nq≈20K) (b)
Tweets(nq≈120K) (c)
Weibo(nq≈120K)


### 6.2. Effect of Coarsening

As mentioned above, we adopt coarsening technique so as to improve the efficiency for large-scale social networks. In this part, we did a series of experiments on Weibo, a large-scale network with about a million users. In order to justify how the parameterr in coarsening method will affect the target influence spread of seeds, we report theRelative Error, which measures the gap between the real influence spread of seed set we get and its estimated influence spread. We set k=300 and the target region as the whole network. Figure 5(a) shows the relative error is decreasing when r becomes bigger. When r=16, the estimated influence spread of seeds using our algorithm with coarsening is nearly equal to the eventual influence spread of seeds without coarsening. Figures 5(b) and 5(c) indicate that the running time for coarsening approach is significantly less than that of noncoarsening one, without loss of seed quality.Figure 5
Effect when using coarsening.
(a)
Effect ofr (b)
Influence spread(r=16) (c)
Running time(r=16)


### 6.3. Varying the Size and Shape ofQ

We also conducted another group of experiments by varyingQ in terms of both size and shape. Specifically, we vary Q as triangle, tetragon, and pentagon, respectively. For each shape, we vary the size at several different levels and report the performance of our algorithm (shown in Figure 6, Q=nq). It justifies that our algorithm can work on target region with arbitrary polygon shapes. Besides, the time spent on the first phase in our algorithm framework increases slightly as the shape of Q varied from pentagon to triangle at the same scale, because nodes in convex hull need to be compared with the polygon queried and the fewer the number of polygon edges, the fewer the comparison times and the less time.Figure 6
Influence spread and running time in terms of size and shape ofQ.
(a)
Gowalla(k=30) (b)
Tweets(k=300) (c)
Weibo(k=300)


## 6.1. Comparison with Baseline

We evaluate the performance of our algorithm frameworkTarIM-SF compared with methodAssembly in [4] under WC model. In order to estimate the performance in general, we selected three regions with fixed nq for each dataset (nq≈20K for Gowalla, nq≈120K for Tweets, and nq≈120K for Weibo) and reported the average performance, while varying k for Gowalla from 10 to 50 and k for Tweets and Weibo from 100 to 500. In Figure 4, we can see that the target influence spread of seeds in our framework is obviously superior to that ofAssembly, especially on Tweets and Gowalla.Figure 4
Influence spread under WC model.
(a)
Gowalla(nq≈20K) (b)
Tweets(nq≈120K) (c)
Weibo(nq≈120K)


## 6.2. Effect of Coarsening

As mentioned above, we adopt coarsening technique so as to improve the efficiency for large-scale social networks. In this part, we did a series of experiments on Weibo, a large-scale network with about a million users. In order to justify how the parameterr in coarsening method will affect the target influence spread of seeds, we report theRelative Error, which measures the gap between the real influence spread of seed set we get and its estimated influence spread. We set k=300 and the target region as the whole network. Figure 5(a) shows the relative error is decreasing when r becomes bigger. When r=16, the estimated influence spread of seeds using our algorithm with coarsening is nearly equal to the eventual influence spread of seeds without coarsening. Figures 5(b) and 5(c) indicate that the running time for coarsening approach is significantly less than that of noncoarsening one, without loss of seed quality.Figure 5
Effect when using coarsening.
(a)
Effect ofr (b)
Influence spread(r=16) (c)
Running time(r=16)


## 6.3. Varying the Size and Shape ofQ

We also conducted another group of experiments by varyingQ in terms of both size and shape. Specifically, we vary Q as triangle, tetragon, and pentagon, respectively. For each shape, we vary the size at several different levels and report the performance of our algorithm (shown in Figure 6, Q=nq). It justifies that our algorithm can work on target region with arbitrary polygon shapes. Besides, the time spent on the first phase in our algorithm framework increases slightly as the shape of Q varied from pentagon to triangle at the same scale, because nodes in convex hull need to be compared with the polygon queried and the fewer the number of polygon edges, the fewer the comparison times and the less time.Figure 6
Influence spread and running time in terms of size and shape ofQ.
(a)
Gowalla(k=30) (b)
Tweets(k=300) (c)
Weibo(k=300)


## 7. Conclusions

In this study, we present a novel model that can address LAIM with a target region that can be an arbitrary polygon. Our framework uses a spatial filtering model to initially figure out the nodes falling into the target polygon. Afterwards, a coarsening process is conducted over the network. Then, the state-of-the-art sampling algorithm adopted in traditional IM is used to find the solution. We theoretically prove the influence spread guarantee in both noncoarsened and coarsened cases. Empirical study over three real-world datasets demonstrates that our framework outperforms the baseline algorithm in terms of influence spread and is efficient in large-scale networks.



---

*Source: 6101409-2018-11-01.xml*