Optimal Region Search with Submodular Maximization

1 Introduction

With the proliferation of mobile devices and Location-Based Services (LBS) (e.g., Google Maps, Foursquare), a huge amount of geo-tagged data are being generated every day. The geo-tagged data has rich information including timestamp, geo-location and comments, which facilitates a large number of location-based applications. As an important problem in LBS, region search has wide applications such as user exploration in a city [Feng et al., 2016; Cao et al., 2014], similar regions query [Feng et al., 2019a], region detection [Feng et al., 2019b], etc.

Most existing studies consider a region as a rectangle with a fixed length and width [Nandy and Bhattacharya, 1995; Choi et al., 2012; Tao et al., 2013; Feng et al., 2016]. It is not general in practice since the regions might be of arbitrary shapes. In order to address this limitation, Cao et al. [Cao et al., 2014] define a region as a connected subgraph and propose the Length-Constrained Maximum-Sum Region (LCMSR) query. It considers two attributes for region search: an objective value of the region computed by summing up the weights of nodes in a region and a budget value by summing up the costs of edges in a region. The target of the LCMSR query is to find the region that has the largest objective value under a given budget constraint.

A simple accumulative function (e.g., SUM) cannot measure the objective value in some applications (e.g., the influence or the diversity of a region [Feng et al., 2016], the likelihood of information [Leskovec et al., 2007], the entropy of locations [Zhang and Vorobeychik, 2016]). In this paper, we use a submodular function to compute the objective score of a region defined as a connected subgraph, which makes the problem more challenging. We denote this problem as optimal region search with submodular maximization (ORS-SM).

We use the example network shown in Figure 1 to illustrate the problem, which consists of 6 locations connected by 8 edges. Each location is associated with some keywords (e.g, mall, coffee) which represent its POI categories, and each edge has a travel time cost. Consider a user travels in a city. She would like to explore the most diversified region to experience the most types of POIs, and she does not want to spend too much time on the road. We can use ORS-SM to find solutions for the user by computing the objective score of a region as the number of different types of POIs contained in the region and setting a travel time limit Δ. Given Δ = 5, LCMSR returns the region R1 = {e1 = (v2, v4), e2 = (v4, v5), e3 = (v4, v6)}, as R1 has the most the number of keywords (not distinct!), but R1 is not the most diversified region since it only contains two types of locations. By contrast, ORS-SM returns R2 = {e1 = (v1, v3), e2 = (v3, v5), e3 = (v4, v5)} which has the most distinct keywords.

As the objective function we use is submodular, the ORSSM problem is a type of submodular optimization [Krause and Golovin, 2014], which are extremely hard [Zeng et al., 2015; Zhang and Vorobeychik, 2016; Stan et al., 2017; Crawford, 2019]. We prove that solving the ORS-SM problem is NP-hard. To our best knowledge, only the Generalized Cost-Benefit Algorithm (GCB) [Zhang and Vorobeychik, 2016] for the problem of submodular optimization with routing constraints can be adapted to solve our ORS-SM problem. The algorithm requires a root node, which does not exist in our problem. Hence, we need to find a tree with the largest objective value by treating each node as root, and the best tree among them is returned as the result for ORS-SM. We denoted this method as GCBAll. GCBAll has a high complexity, so that it has poor efficiency and is not scalable.

To better solve ORS-SM, we propose a 1 O(√Δ/bmin) - approximation algorithm AppORS, where bmin is the minimal cost on edges. We observe that the returned region is always a tree. The basic idea of this algorithm is to first find a set of nodes with large objective scores, and we guarantee that there exists a tree connecting them whose total cost is smaller than the budget limit Δ. Next, we find the best region by using these nodes. Next, we propose another algorithm with the same approximation ratio called IAppORS to further improve the effectiveness of AppORS. This algorithm can obtain regions of better quality.

In summary, the contribution of this paper is threefold. Firstly, we propose ORS-SM through a submodular optimization and prove its NP-hardness. Secondly, we develop two approximation algorithms AppORS and IAppORS for this problem. Finally we conduct experiments on two applications using three real-world datasets and demonstrate the efficiency and accuracy of the proposed algorithms.

2 RelatedWork

Region search has been well studied and has a wide range of applications such as user exploration in a city [Feng et al., 2016; Cao et al., 2014], similar regions search [Feng et al., 2019a], region detection [Feng et al., 2019b], etc.

Most existing region search problems consider the region as size-fixed rectangles or radius-fixed circles. The Max-Enclosing Rectangle (MER) problem [Nandy and Bhattacharya, 1995] aims to find a rectangle with a given size a × b such that the rectangle encloses the maximum number of spatial objects. This problem is systematically studied as the maximizing range sum problem [Choi et al., 2012; Tao et al., 2013]. The similar region search [Feng et al., 2019a], bursty region detection [Feng et al., 2019b], and the best region search [Feng et al., 2016] also consider regions as rectangles. However, as shown in the study of the LCMSR query proposed by Cao et al. [Cao et al., 2014], in practice the regions are usually arbitrarily shaped. LCMSR defines a region as a connected subgraph with relevant objects. It uses a sum function to accumulate the weights of objects in the region, and it aims to find the optimal region that has the largest total weight and does not exceed a size limit. We use a submodular function to compute the objective value for a region and aim to maximize this value under a budget constraint, which makes the problem more challenging.

Our work is also related to submodular optimization which has breadth of applicability with applications including viral marketing [Kempe et al., 2003], recommendation system [Chen et al., 2015], information gathering [Leskovec et al., 2007], deep neural network training [Joseph et al., 2019], etc. A large amount of research considers submodular optimization under constraints, such as cardinality constraint [Kempe et al., 2003], cost constraint [Qian et al., 2017], routing constraint [Zeng et al., 2015; Zhang and Vorobeychik, 2016], connectivity constraint [Kuo et al., 2014], and so on. Submodular Optimization under Connectivity Constraint (SOCC) [Kuo et al., 2014] is similar to our problem, but it considers the cost on nodes to compute the budget values. In contrast, the budget values are associated with edges in our problem, and thus the algorithms for SOCC is not feasible to solve ORS-SM.

3 ProblemFormulation

In this section, we formally define the problem of optimal region search with submodular maximization (ORS-SM) and prove its hardness. The problem is defined over a spatial network G = (V, E), where V is a set of nodes and E ⊆ V × V is a set of edges. Each node v ∈ V represents a location, and each edge 〈vi, vj〉 ∈ E represents an undirected path between two locations vi and vj in V associated with a cost b(vi, vi+1) (representing the distance, the travel time, etc.).

Definition 1. Region. Given a spatial network G = (V, E), a region R is a connected subgraph of G. We denote the nodes and edges in R as R.V and R.E respectively.

In order to measure the quality of a region, we consider two values, namely the budget value and the objective value. The budget value is defined as the sum of the costs on all the edges in the region, which is computed as:

The objective value is computed by a submodular function f() over the set of locations in a region (e.g., the number of distinct keywords, the social influence, etc.):

OS(R) is submodular means that OS(R1 ⋃ vi)-OS(R1) ≥ OS(R2 ⋃ vi) -OS(R2), for all R1 ⊆ R2 and vi ̸∈ R1, and R1(R2) ⋃ vi composes a new region.

For example, we consider a problem of finding the most diversified region in a network G as shown in Figure 1. In this example, the objective value is computed as OS(R) = | ∪vi∈R.V K(vi)|, where K(vi) is the set of distinct keywords on vi. For R2 in the example, we can get OS(R2) = |{bar, coffee, park, mall}| = 4 and BS(R2) = 5.

Formally, we define the ORS-SM problem as follows:

Definition 2. Optimal Region Search with Submodular Maximization (ORS-SM). Given G = (V, E), and a budget constraint Δ, we aim to find the region R such that

Theorem 1. Solving the ORS-SM problem is NP-hard.

Proof. The LCMSR query [Cao et al., 2014] which is mentioned in the Introduction is a special case of ORS-SM, because the sum function also satisfies the submodular properties. As the LCMSR problem is proved to be NP-hard, the ORS-SM problem is NP-hard as well. ■

4 Approximation AlgorithmAppORS

In this section, we propose a novel approximation algorithm called AppORS for solving the ORS-SM problem, and we also prove its error bound. For any subgraph region Ri, we can always find its minimum spanning tree Ti such that BS(Ti) ≤ BS(Ri) and OS(Ti) = OS(Ri). Hence, the optimal region of the ORS-SM problem must be a tree, and we consider the tree search in the subsequent discussions directly. Before presenting the algorithm, we first introduce the following lemma which lays the foundation of our algorithm.

Lemma 1. For any tree T = (VT , ET ) with budget value BS(T ), there always exist n ≤ max(10⌊ BS(T ) m ⌋, 2) subtrees Ti = (VTi , ETi ), 1 ≤ i ≤ n, such that BS(Ti) ≤ m if |ETi | > 1 and ∪ni=1VTi = VT .

Proof. We utilize the claim 3 of the Maximum Connected Submodular set function with Budget constraint problem (MCSB) [Kuo et al., 2014], and we conduct the proof through the following steps:

1) Given a graph G = (V, E), we can get its line graph GL = (V L, E L). For a tree T = (VT , ET ) with the budget value BS(T) in G, we can get its corresponding subgraph GLT in G L. If GLT contains cycles, we break cycles by removing some edges. After that, we get a tree T L = (VT L, ET L) spanning all nodes of GLT . Now each edge in T corresponds to a node in T L.

2) According to the claim 3 for MCSB, for T L with budget value BS(T L), there always exist n = max(5⌊ BS(T L ) m ⌋, 1) subtrees T L i = (VT L i , ET L i ), such that BS(T L i ) ≤ m + BS(rL i ) and ∪ni=1VT L i = VT L, where rL i is the root of T L i for all 1 ≤ i ≤ n. For each subtree T L i , if VT L i > 1, we can always select a node with degree 1 as rL i , and we can then divide it into two subtrees T 1,L i consisting of rL i and T 2,L i consisting of the remaining of VT L i . Hence, we know that BS(T 2,L i ) ≤ m. After that, we can obtain n ≤ max(10⌊ BS(T L ) m ⌋, 2) subtrees T ′Li = (VT ′Li , ET ′Li ), such that BS(T ′Li ) ≤m if |VT ′Li | > 1 and ∪ni=1VT ′Li = VT L .

3) For each subtree T ′Li , we find its line graph Gi. As T ′Li is obtained from the line graph of G, Gi must be a subgraph of the original tree T in the first step. Based on translated properties of a line graph, i.e., the the line graph of a connected graph is connected, Gi must be connected. Thus, each Gi must be a tree as well and we denote it as Ti, and we have ∪ni=1VT L i = VT L = ET . We thus complete the proof. ■

Now we are ready to present our approximation algorithm AppORS. The basic idea of AppORS is to find a tree T ∗ , such that OS(T ∗ ) is larger than the objective score of any subtree Ti whose budget score is no larger than m and BS(T ∗ ) ≤ Δ. We then can prove that the region R∗ obtained based on T ∗ is an approximate feasible solution of the problembased on Lemma 1. In AppORS, Nemhauser's greedy algorithm [Nemhauser et al., 1978] is used to to solve the Maximum Rooted Submodular set function (MRS) problem [Kuo et al., 2014], which aims to find a node set containing a given root node and other K-1 nodes such that the score computed

Algorithm 1: AppORS Algorithm

Input: G = (V, E), Δ Output: A region R∗ 1 Initialize a node set V K opt ← ∅, vopt ← ∅; 2 K ← ⌈√ Δ bmin ⌉ +1, DisLim← √Δbmin; 3 for each node vi ∈ V do 4 Vvi ← {vj|vi ̸= vj, dis(vi, vj) ≤DisLim}; 5 Use Nemhauser's greedy algorithm to solve MRS(OS(·), Vvi , K, vi), and get top-K node set V K vi ; 6 if OS(V K opt) < OS(V K vi ) then 7 V K opt ← V K vi , vopt ← vi; 8 T ∗ ← findOptTree(V K opt, G, Δ, vopt); 9 T ′ ← a single edge in E with the maximum OS value and BS(T ′ ) ≤ Δ; 10 R∗ ←T ∗ if OS(T ∗ ) ≥ OS(T ′ ) else T ′ ;

• 11 return the region R∗ ;

by a submodular function over the K nodes is maximum.

As shown in Alg.1, AppORS starts with an initial node set V K opt , a root node vopt, two parameters K and DisLim (lines 1-2), where bmin = min(vi,vj)∈Vb(vi, vj). After that, for each node vi ∈ V, AppORS first finds the candidate node set Vvi in which each node has a distance to vi smaller than DisLim (lines 3-4). Then AppORS constructs a MRS problem instance MRS(OS(·), Vvi , K, vi), and then uses the Nemhauser's greedy algorithm to solve the instance for getting a top-K node set V K vi (line 5). If OS(V K opt ) < OS(V K vi ), AppORS updates V K opt and vopt (lines 6-7). Next, AppORS uses function findOptTree(V K opt , G,Δ, vopt) to find a tree T ∗ spanning all nodes in V K opt , satisfying BS(T ∗ ) ≤ Δ (line 8). After that, AppORS finds T ′ consisting of a feasible edge by scanning all edges in E which has the maximum objective score (line 9). Finally, it returns the tree with the larger objective value as the region R∗ (lines 10-11). One simple method of implementing findOptTree(V K opt , G,Δ, vopt) is to find all shortest paths from vopt to all nodes in V K opt , and then get a tree T ∗ by removing duplicate edges in the shortest paths. We will present a better method in Section 5.3.

We analyze the error bound of AppORS as below.

Lemma 2. AppORS returns a feasible solution of the ORSSM problem.

Proof. In AppORS, BS(T ′ ) ≤ Δ. And V K opt contains K nodes, the largest distance between vopt and vj ∈ V K opt is DisLim. Thus, in the tree T ∗ is achieved by combining all shortest paths from vopt to all nodes in V K opt , BS(T ∗ ) ≤ (K1) ∗ DisLim = Δ. ■

Lemma 3. OS(Ropt) ≤ O(√Δ/bmin)OS(R∗ ), where Ropt denotes the optimal region of the ORS-SM problem.

Proof. We denote the optimal solution of MRS(OS(·), Vvi ,K, vi) as V MRS opt , the optimal tree rooted at vi whose budget value under DisLim as T vi,DL, and T vi,DL with the maximal objective value as T vi,DL opt . We can get that T vi,DL opt has at most ⌊ DisLim bmin ⌋ nodes except vi, and these nodes are in {vj|dis(vi, vj) ≤ DisLim}. And ⌊ DisLim bmin ⌋ ≤ ⌊√ Δ bmin ⌋ ≤ K - 1. For any node vj ∈ T vi,DL opt , vj ∈ Vvi . Thus, OS(V MRS opt ) ≥ OS(T vi,DL opt ). Meanwhile, in AppORS, OS(T ∗ ) ≥ OS(V K opt ). And based on Lemma 2 in [Kuo et al., 2014], Nemhauser's greedy algorithm can get a e-1 e -approximate solution for the MRS problem, we have OS(V K opt ) ≥ e-1 e OS(V MRS opt ). Hence we can get OS(T ∗ ) ≥ e-1 e OS(T vi,DL opt ).

As Ropt must be a tree, we use Topt to represent it. According to Lemma 1, for Topt = (VTopt , ETopt ) with the budget value Topt, there always exist n ≤ max(10⌊ Δ DisLim ⌋, 2) subtrees Ti = (VTi , ETi ), where BS(Ti) ≤ DisLim if |ETi | > 1, such that ∪ni=1VTi = VTopt . Hence, we have:

where the first inequality is derived from the property of the submodular function OS(·). ■

Based on Lemma 2 and 3, we can obtain Theorem 2:

Theorem 2. AppORS is a 1 O(√Δ/bmin) -approximation algorithm for the ORS-SM problem.

Proof. It is obvious since AppORS returns a feasible solution whose objective score is no smaller than 1 O(√Δ/bmin) times

of the optimal value. ■

5 Improved AppORS

As AppORS considers the worst case to compute K nodes under the budget constraint and only searches within Vvi = {vj|dis(vi, vj) ≤ DisLim}, it cannot achieve high-quality solutions in practice (as shown in the experimental study). To improve the solution quality of AppORS, we present an Improved version of AppORS (IAppORS). Meanwhile, we develop two heuristic methods to implement a key function of IAppORS.

5.1 An Improved Version of AppORS

We abbreviate lines 3-7 of Alg. 1 as: for each node vi ∈ V do update(vopt, V K opt ). In the improved version of AppORS, the details of the new update(vopt, V K opt ) function are shown in Alg. 2. Different to the old function, the new one improves the solution quality by using a method findFeaNodeSet(vi, G,Δ) to find another feasible node set V 2,K vi (lines 4-6). Note that, iff V 2,K vi has a tree T 2,K vi spanning its all nodes, and BS(T 2,K vi ) ≤ Δ, V 2,K vi is a feasible node set.

Theorem3. IAppORS returns a 1 O(√Δ/bmin) -approximation solution of the ORS-SM problem.

Proof. As both of V 1,K vi and V 2,K vi are feasible node sets, IAppORS can find a feasible solution for the ORS-SM problem. Meanwhile, the solution quality of IAppORS is not worse than that of AppORS. This leads to the final conclusion. ■

Algorithm 2: New update(vopt, V K opt )

Input: G = (V, E), Δ, K, DisLim, vi, vopt, V K Output: Updated vopt, V K

vi ;

• opt opt 1 V 1 vi ← {vj |vi ̸= vj , dis(vi, vj ) ≤ DisLim}; 2 Use Nemhauser's greedy algorithm to solve MRS(OS(·), V 1 vi , K, vi), and get topK node set V 1,K 3 V K vi ← V 1,K vi ; 4 V 2,K vi ← findFeaNodeSet(vi, G,Δ); 5 if OS(V K vi ) < OS(V 2,K vi ) then 6 V K vi ← V 2,K vi ; 7 if OS(V K opt) < OS(V K vi ) then 8 V K opt ← V K vi , vopt ← vi; 9 return vopt, V K opt ;

5.2 Two Heuristic Methods for IAppORS

To implement findFeaNodeSet(vi, G,Δ) in IAppORS, we present two heuristic methods. At first, we introduce the function compute(BS(Vi)) which is used to compute the minimal budget value of the tree spanning all nodes in the node set Vi. compute(BS(Vi)) is a Steiner tree problem which is proved to be NP-hard [Vazirani, 2013]. Rather than computing accurate BS(Vi), we use an approximation algorithm to get an estimated value ˆ BS(Vi). Here, we use Kruskal's algorithm to compute a Minimum-cost Spanning Tree (MST) for spanning all nodes in BS(Vi), as we can utilize the MST to obtain a 2-approximation solution for the Steiner tree problem [Vazirani, 2013], and Kruskal's algorithm is efficient. We denote this method as compute( ˆ BS(Vi)).

Next, we present the first implementation of findFeaNodeSet1(vi, G,Δ). As shown in Alg. 3, it begins with initializing node sets V 2,K vi and V 2 vi (lines 1). In each while loop, the method selects a node vmax with the maximum marginal objective value for the current V 2,K vi from V 2 vi . After that, the method removes vmax from V 2 vi and computes ˆ BS(V 2,K vi ∪ vmax) by utilizing the Kruskal's algorithm. If the estimated budget value is not larger than Δ, vmax would be inserted into V 2,K vi . The process is terminated when V 2 vi = ∅ (lines 2-7). At the last step, the method returns a node set V 2,K vi .

Algorithm 3: Function f indF eaNodeSet1(vi, G, Δ)

Input: G = (V, E), Δ, vi Output: V 2,K vi 1 V 2,K vi ← {vi}, V 2 vi ← {vj |vi ̸= vj , dis(vi, vj ) ≤ Δ}; 2 while V 2 vi ̸= ∅ do 3 vmax ← argmaxOSvj∈V2 vi (V 2,K vi ∪ vj); 4 V 2 vi ← V 2 vi \ vmax; 5 ˆ BS(V 2,K vi ) ← compute( ˆ BS(V 2,K vi ∪ vmax)); 6 if ˆ BS(V 2,K vi ∪ vmax) ≤Δ then 7 V 2,K vi ←V 2,K vi ∪ vmax; 8 return V 2,K vi ;

Note that, as BS(V 2,K vi ∪ vmax) ≤ ˆ BS(V 2,K vi ∪ vmax), and thus we have BS(V 2,K vi ∪ vmax) ≤ Δ. So that V 2,K vi is a feasible solution of the ORS-SM problem. In addition, we can speed up the process of findFeaNodeSet1(vi, G,Δ) using an optimization technique called Lazy Evaluations [Leskovec et al., 2007]. We denote IAppORS with f indF eaNodeSet1(vi, G, Δ) as IAppORSHeu1.

Next, we propose another heuristic method to implement findFeaNodeSet(vi, G,Δ) which is faster than the first one. Intuitively, for two nodes v1 and v2, when dis(v1, v2) is smaller, the difference between V 2,K v1 and V 2,K v2 is smaller. Thus, we can use V 2,K v1 to approximate V 2,K v2 . Based on this observation, we present the second method findFeaNodeSet2(vi, G,Δ). The most steps are similar to Alg. 3, but the line 4 is replaced by V nei vi ← {vj |dis(vi, vj ) ≤ γΔ}, V 2 vi ← V 2 vi \ {V nei vi ∪ vmax}, where γ ∈ (0, 1] is a parameter, and V nei vi is the neighbor node set of vi. In this way, we use the seconde feasible node set of vi as those of vi's neighbor nodes, and reduce the related computations. We denote IAppORS with f indF eaNodeSet2(vi, G, Δ) as IAppORSHeu2, and V 2,K vi in IAppORSHeu2 is also a feasible node set.

In this section, we present a better method to implement the function f indOptT ree(V K opt , G, Δ, vopt) in line 8 of Alg. 1.

We first compute the shortest distances between each pair of nodes using some existing methods. Then, we use the Kruskal's algorithm to find a MST (denoted as MST1) spanning all nodes in V K opt , and MST1 contains unknown shortest paths between some pairs of nodes. Next, we find the real shortest paths by inserting the node set Vmid = {vi|vi ∈ Vvopt , ˆ BS(V K opt ∪ vi) = ˆ BS(V K opt )} into V K opt , and finding a new MST (denoted as MST2) spanning all nodes in MST2, where Vvopt ← {vi|vi /∈ V K opt , dis(vopt, vi) ≤ Δ}.

MST2 is a feasible solution for the ORS-SM problem, but its budget value may be far less than Δ. We improve MST2 by extending it greedily. In each iteration, we select a node which is connected to MST2 and has the maximum marginal objective value, and insert the node intoMST2. The process is repeated until no more nodes can be added into MST2. Finally, we can get a better region MST2 from V K opt . Thus, we use this method to do findOptTree(V K opt , G, Δ, vopt) for all proposed algorithms by default.

5.4 Time Complexity of the Proposed Algorithms

In this section, we analyze the complexity of all the proposed algorithms AppORS, IAppORSHeu1 and IAppORSHeu2. These algorithms have two main steps. Step1 computes a feasible node set V K opt , and Step 2 searches a feasible spanning tree T ∗ from V K opt and T ′ consisting of one edge. We denote the time cost of computing dis(vi, vj ) as tdis. AppORS needs |V| loops in Step 1, and in each loop, it takes O(|V|tdis) time to get the candidate node set Vvi , and costs O(K|Vvi |max) time to get top-K node set and update V K opt and vopt, where |Vvi |max is the maximum value of |Vvi |. The method in Section 5.3 is the default method used in Step 2. It first takes O(|V K opt |2 log|V K opt |) time to find MST1. After that, it costs O(|V|tdis) time to get the node set Vvopt , and then costs O(|Vvopt ||V K opt |2 (tdis + log|V K opt |)) time to get MST2. Next, it requires O(|Vvopt ||V K opt |) time to extend MST2. Finally, it takes O(|E|) time to find T ′ . Thus, the time complexity of AppORS is O(|V|2 tdis + |Vvopt ||V K opt |2 (tdis + log|V K opt |)).

IAppORSHeu1 also needs |V| loops in Step 1. In each loop, it first takes O(|V|tdis) time to get V 1,K vi , and then costs O(|V|tdis + |V 2 vi |max(|V 2,K vi |max)2 (tdis + log|V 2,K vi |max)) time to get V 2,K vi , Step 2 of IAppORSHeu1 is the same to that of AppORS, and the worst case of IAppORSHeu2 is IAppORSHeu1. Therefore, the time complexity of IAppORSHeu1 and IAppORSHeu2 is O(|V|2 tdis + |V||V 2 vi |max(|V 2,K vi |max)2 (tdis + log|V 2,K vi |max)).

6 Experimental Study

We compare the proposed algorithms to the state-of-the-art algorithm GCBAll in two applications on three real-world datasets. As discussed in Section 1, GCBAll is the adapted version of GCB [Zhang and Vorobeychik, 2016] for solving our ORS-SM problem. In GCBAll, to compute an approximation of the minimal budget value of a tree spanning all the given nodes, we adopt the 2-approximation algorithm for the Steiner tree problem [Vazirani, 2013] by utilizing the minimum spanning tree. We implement all the algorithms in JAVA on Windows 10, and run on a server with an Intel(R)Xeon(R) W-2155 3.3GHz CPU and 256 GB memory.

6.1 Case Study 1: Most Influential Region Problem Definition and Datasets

We first investigate the Most Influential Region Search (MIRS) which aims to find an optimal region under a budget constraint such that the number of affected users is maximal in a geo-social network. This problem is useful in many scenarios, e.g., a company wants to find a region for marketing its products, the government intends to find a region for building some public facilities, etc. We model the geo-social network as an undirected graph G = (V, E) and compute the probability that a user ui visits a region R as P R ui = 1 - ∏vj ∈R.V (1 - P vj ui ), where P vj ui is the probability that ui visits the location vj, and it is computed as P vj ui = # of check-ins in vj of ui # of check-ins of ui . Thus, the objective value of R is the number of users expected to be affected by R, and it is computed as a submodular function: OS(R) = ∑ui∈U P R ui , where U represents all users.

In this problem, we use two real-world datasets SG and AS crawled from FourSquare (also used in the work [Zeng et al., 2015]), in which SG has 189,306 check-ins made by 2,321 users at 5,412 locations in Singapore, and AS contains 201,525 check-ins made by 4,630 users at 6,176 locations in Austin. Following the work [Zeng et al., 2015], we make an edge between two locations which were visited continuously in one day by the same user, and use the Euclidean distance as the budget value for each edge. We also removed the checkins made by users who checked in a location less than 3 times.

Performance of Our Methods

We compare three proposed algorithms with GCBAll in terms of efficiency (the run time) and effectiveness (the objective score) by varying Δ from 20km to 60km. Fig. 2 shows that GCBAll is rather time-consuming when Δ is large, as it calls compute( ˆ BS(Vi)) too many times and cannot use Lazy Evaluations optimization [Leskovec et al., 2007] to find vmax quickly. All the proposed algorithms are faster than GCBAll more than one order of magnitude. Meanwhile, the objective scores of IAppORSHeu1 and IAppORSHeu2 are relatively high (more than 90% of GCBAll), which is also consistent with our theoretical analysis of the solution quality. The results demonstrate that two presented heuristic methods can improve the solution quality of AppORS significantly. The experimental results also show that the solution quality of our algorithms is better than that of GCBAll within a run time limit (e.g., 1s, 5s, 10s). We omit these results here due to the space limitation.

6.2 Case Study 2: Most Diversified Region

Problem Definition and Datasets

The second application Most Diversified Region Search (MDRS) is to find the most diversified region under a budget constraint. We consider MDRS on road networks which contains a set of locations associated with a set of keywords (e.g., mall and bar). We measure the diversity of a region using the number of different keywords, and thus the objective function is OS(R) = | ∪vi∈R.V K(vi)|, where K(vi) is the set of keywords on vi.

We use the road network in California (CA) from a public website 1 . We then utilized the Foursquare APIs to fill in the missing keywords for nodes (categories of locations) 2 . CA contains 21,048 nodes and 22,830 edges [Li et al., 2005].

Performance of Our Methods

As GCBAll cannot find results under Δ = 30km on AS within 1, 000s and CA is even larger than AS, we only compare the performance of the three proposed algorithms on a larger Δ using CA. As shown in Fig. 3, the objective scores of IAppORSHeu1 and IAppORSHeu2 are competitive, and higher than that of AppORS. Meanwhile, IAppORSHeu2 is faster than IAppORSHeu1 by about one order of magnitude, and can solve the problem with 4s when Δ = 100km.

1 http://www.cs.utah.edu/ lifeifei/SpatialDataset.htm

2 https://developer.foursquare.com/docs/api

In addition, to compare the performances of the three algorithms by varying the dataset size, we generate a synthetic dataset (denoted as SY ) based on the structure of the CA dataset. Next, we run the three algorithms on SY by varying the number of nodes from 10,000 to 30,000, and set Δ = 60km. Fig. 4 shows that the run time of IAppORSHeu2 grows slowly with the increasing number of nodes, and the solution quality of IAppORSHeu2 is close to that of IAppORSHeu1, and better than that of AppORS.

7 Conclusion

We propose the ORS-SM problem which aims to find the optimal region such that it maximizes the objective score of a the region computed by a submodular function subject to a given budget score constraint. To efficiently solve the ORS-SM problem, we propose two approximation algorithms and further improve them with some optimization techniques. The results of empirical studies on two applications using three real-world datasets demonstrate the efficiency and the solution quality of our proposed algorithms. In future work, we would like to design an efficient index to improve the efficiency and scalability of the proposed methods.

Acknowledgements

Xin Cao is supported by ARC DE190100663. Yifeng Zeng is supported by EPSRC-EP/S011609/1. Bin Yao is supported by NSFC (No. U1636210, 61729202, 61922054, 61872235, 61832017), The National Key Research and Development Program of China (2018YFC1504504). Xin Cao is the corresponding author of this paper.