Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information, or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture user's influence propagation in the future period as well. In this paper, we target a new research problem, named Reconnecting Top-l Relationships (RTlR) query, which aims to find l number of previous existing relationships but being stranged later, such that reconnecting these relationships will maximize the expected benefit of influenced users by the given group in a future period. We prove that the RTlR problem is NP-hard. An efficient greedy algorithm is proposed to answer the RTlR queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RTlR queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.


INTRODUCTION
Over the past few decades, the rise of online social networks has brought a transformative effect on the communication and information spread among human beings. Through social media platforms (e.g., Twitter), business companies can spread their products information and brand stories to their customers, politicians can deliver their administrative ideas and policies to the public, and researchers can post their upcoming academic seminars information to attract their peers around the world to attend. Motivated by real substantial applications of online social networks, researchers start to keep a watchful eye on information diffusion [4,23], as the information could quickly become pervasive through the "word-of-mouth" propagation among friends in social networks.
Influence Maximization (IM) is the key algorithmic problem in information diffusion research, which has been extensively studied in recent years. IM aims to find a small set of highly influential users such that they will cause the maximum influence spread in a social network [3,23,37,40]. To fit with different real application scenarios, many variants of the IM problem have been investigated recently, such as Topic-aware IM [5,17,29,30], Time-aware IM [14,20,39,47], Community-aware IM [28,42,45,48], Competitive IM [2,32,36,43], Multi-strategies IM [7,24], and Out-of-Home IM [51,53]. However, some critical characteristics of the IM study fail to be fully discussed in existing IM works. We explain these characteristics using the two observations below.
Observation 1. Some business companies wish their product information would be spread to most of their customers in the period after they spent their budgets on their selected seed users (e.g., Apple releases its new iPhone every September. They want to find optimal influencers in social networks to appeal to as many users as possible to purchase the new iPhone in the year ahead). However, most of the existing IM works modelled the social networks as static graphs, while the topology of social networks often evolves over time in the real world [8,26]. Therefore, the seed users selected currently may not give good performance for influence spread in the following time period due to the evolution of the network. To satisfy Apple's requirement, we would better predict the topology evolution of social networks in the following period and select seed users from the predicted network.
Observation 2. Existing IM studies dedicated to the influence maximization problem depend on a strong assumption -the selected seed users will spread the information. However, some of the chosen individual seed users may be unwilling to promote the product information for various reasons. Moreover, most startups and academic groups may not have the budget to motivate the seed users to spread their product or academic activities information.
Our Problem. The aforementioned observations motivate us to propose and study a novel research problem, namely Reconnecting Top-Relationships (RT R). Given a directed evolving graph G = { } −1 0 , a parameter , and an institute U contains a group of users, RT R asks for reconnecting a set of estranged relationships (e.g., edges that have ever existed in G while disappearing in the near future snapshot graph ). Reconnecting the selected edges in RT R query to will maximize the number of influenced users in that are influenced by the members of U.  Note: the given users' group U are marked as black icons and covered by blue color, 0 is the snapshot of the directed evolving graph G = { } −1 0 at time 0, and is the predicted graph snapshot of G at time ; the greyish dotted edges in represent the relationship between users exists in G while disappearing in ; the purple dotted lines represent the new adding edges in ; the edge of two red icons which covered by yellow color is the query result of RT R problem. Example 1.1 (Motivation). LinkedIn 1 is a business and employment oriented online social network. It provides a social network platform to allow members to create their profiles and "connect" to each other, representing real-world professional relationships. Members can also post their activity information (e.g., employment Ads) on LinkedIn. The study of RT R can significantly enhance the stickiness of members in LinkedIn without any budgets paid by members or LinkedIn itself. Figure 1 presents an evolving social network with ten members and their relationships. Suppose a research group (e.g., black icons) will host an online virtual academic seminar next month. They post the seminar information on LinkedIn because they wish to attract as many researchers as possible to join their seminar in the month ahead (e.g., ). By answering the RT R query, LinkedIn can find out the optimal estranged relationships (e.g., among the greyish dotted edges), in which reconnecting them (e.g., red icons) will maximize the spread of seminar information in the coming month. To reconnect the estranged relationships, a possible way is to send an email to the related users' platform Inbox and notify them of the recent news of their old friends. Therefore, the study of RT R query will benefit both users and the social media platform. The members will be more willing to keep active in the network platforms, which provide them a free and efficient information post service.
To the best of our knowledge, this is the first IM study that draws the inspiration from the intersection of (1) topology evolving prediction of social networks, and (2) no additional cost. As a result, the following challenges are important to be addressed. Challenges. The first challenge is how to predict the topology of social networks in a specified future period. To deal with this challenge, we adopt the link prediction method [50] to predict the network structure evolution in evolving networks. The other challenge is the complexity of RT R query problem. Unlike traditional IM studies that aim to find Top-influential users, our RT R focuses on the edges discovery. The existing IM algorithms are not applicable to address the RT R query, and a more detailed analysis 1 https://www.linkedin.com/ the number of generated sketch subgraphs in the SBG method is presented in Section 4.1. Thirdly, our RT R query may return different results for different given user groups, while the IM problem only needs to be queried one time to get the most influential users.
To address these algorithmic challenges, we first propose a sketchedbased greedy (SBG) algorithm to answer the RT R query of a given group. Besides, a candidate edges reducing method has been proposed to boost the SBG algorithm's efficiency. Furthermore, we carefully designed a novel order-based SBG algorithm to accelerate the RT R query. Contributions. We state our major contributions as follows: • We introduce and formally define the problem of Reconnecting Top-Relationships (RT R) for the first time, and explain the motivation of solving the problem with real applications. We also prove that the RT R query problem is NP-hard. • We propose a sketch-based greedy (SBG) approach to answer the RT R queries. Besides, we present the pruning method to boost the efficiency of the SBG algorithm by reducing the number of candidate edges' probing. • To further accelerate the RT R query, we elaborately design a novel order-based algorithm to answer the RT R query more efficiently. • We conduct extensive experiments to demonstrate the efficiency and effectiveness of our proposed algorithms using real-world datasets.
Organization. The remainder of this paper is organized as follows. First, we present the preliminaries in Section 2 and formally define the RT R problem in Section 3. Then, we propose the sketch-based greedy approach and the accelerate method in Section 4. We further present a new order-based algorithm to efficiently answer the RT R query in Section 5. After that, the experimental evaluation and results are reported in Section 6. Finally, we review the related works in Section 7 and conclude this work in Section 8.
We define a directed evolving network as a sequence of graph snapshots G = { } −1 0 , and {0, , 1, .., − 1} is a set of time points. We assume that the network snapshots in G share the same vertex set. Let represent the network snapshot at timestamp ∈ [0, −1], where each vertex in is a social user in , each edge = ( , ) in represents a cyber link or a social relationship between users and in . Similar to [11,21], we can create "dummy" vertices at each time step to represent the case of vertices joining or leaving the network at time (e.g., where is the set of vertices truly exist at ). Besides, each edge ( , ) ∈ in is associated with a propagation probability ( , ) ∈ [0, 1]. Table 1 summarizes the mathematical notations frequently used throughout this paper.

Link Prediction
Link prediction is an important network-related problem firstly proposed by Liben-Nowell et al. [31], which aims to infer the existence of new links or still unknown interactions between pairs of nodes based on their properties and the currently observed links.
Given a directed evolving graph G = −1 0 with the time points set {0, 1, .., − 1}, in this paper, we use the recent link prediction method [49,50], named learning from Subgraphs, Embeddings, and Attributes for Link prediction (SEAL) method, to predict the graph structure of snapshot graph of G at the future time point . Specifically, SEAL is a graph neural network (GNN) based link prediction method that transforms the traditional link prediction problem into the subgraph classification problem. It first extracts the ℎ-hop enclosing subgraph for each target link, and then applies a labeling trick, called Double Radius Node Labeling (DRNL), to add an integer label for each node relevant to the target link as its additional feature. Next, the above-labeled enclosing subgraphs are fed to GNN to classify the existence of links. Finally, it returns the predicted graph of evolving graph G at time point .

Influence Maximization (IM) Problem
To better understand the IM problem, we first introduce the influence diffusion evaluation of given users. The independent cascade (IC) model [23] is the widely adopted stochastic model which is used for modeling the influence propagation in social networks. In the IC model, for each graph snapshot , the propagation probability ( , ) of an edge ( , ) is used to measure the social impact from user to . This probability is generally set as ( , ) = 1 ( ) , where ( ) is the degree of . Every user is either in an activated state or inactive state. 0 be a set of initial activated users, and generates the active set for all time step ≥ 1 according to the following randomized rule. At every time step ≥ 1, we first set to be −1 ; Each user activated in time step has one chance to activate his or her neighbours with success probability ( , ). If successful, we then add into and change the status of to activated. This process continues until no more possible user activation. Finally, is returned as the activated user set of 0 .
Let ( , ) be the number of vertices that are activated by in graph snapshot on the above influence propagation process under the IC model. The IM problem aims to find a size-seed set with the maximum expected spread ( ( , )). We define the IM problem as follows: Definition 2.1 (IM problem [23]). Given a directed graph snapshot = ( , ), an integer , the IM problem aims to find an optimal seed set * satisfying, Let be the maximum expected spread of any size-seed set, then we have = ( ( * , )).

Reverse Reachable Sketch
The Reverse Influence Set (RIS) [3] sampling technique is a Reverse Reachable Sketch-based method to solve the IM problem. By reversing the influence diffusion direction and conducting reverse Monte Carlo sampling [25], RIS can significantly improve the theoretical run time bound.
Definition 2.2 (Reverse Reachable Set [3]). Suppose a user is randomly selected from . The reverse reachable (RR) set of is generated by first sampling a graph from , and then taking the set of users that can reach to in .
By generating 1 RR sets on random users, we can transform the IM problem to find the optimal seed set , while can cover most RR sets. This is because if a user has a significant influence on other users, this user will have a higher probability of appearing in the RR sets. Besides, Tang et al. [41] proved that when 1 is sufficiently large, RIS returns near-optimal results with at least 1− | | −1 probability. Therefore, the process of using the RIS method to solve the IM query contains the following steps: 1 Generate 1 random RR sets from . 2 Find the optimal user set which can cover the maximum number of above generated RR sets. 3 Return the user set as the query result of IM query problem. Theorem 2.1 (Complexity of RIS [40]). If 1 ≥ (8 + 2 ) · | | · | | + | | + 2 · 2 , RIS returns an (1 − 1 − ) approximate solution to the IM problem with at least 1 − | | −1 probability.

Forward Influence Sketch
The Forward Influence Sketch (FI-SKETCH) method [9, 10, 35] constructs a sketch by extracting the subgraph induced by an instance of the influence process (e.g., the IC model). Then, it can estimate the influence spread of a seed set using these subgraphs accurately with theoretical guarantee. The process of using the FI-SKETCH method to solve the IM query contains the following steps: 1 Generate 2 sketch subgraph by removing each edge = ( , ) from with probability 1 − , . 2 Find the optimal user set , while the average number of users reached by within 2 constructed sketches graphs is maximum. 3 Return the user set as the query result of IM query problem. Theorem 2.2 (Complexity of FI-SKETCH [9]).
) approximate solution to the IM problem with at least 1 − | | −1 probability.

PROBLEM DEFINITION
In this section, we formulate the Reconnecting Top-Relationships (RT R) query problem and analyze its complexity. Definition 3.1 (RT R Problem). Given a directed evolving graph G = { } −1 0 , the parameter , and a group of users U, the problem of Reconnecting Top-Relationships (RT R) asks for finding an optimal edge set with size in predicted graph snapshot of G at time , where the expected spread of U will be maximized while reconnecting edges of in (e.g., = ⊕ ). Formally, In the following, we conduct a theoretical analysis on the hardness of the RT R problem.
Proof. We prove the hardness of RT R problem by a reduction from the decision version of the maximum coverage (MC) problem [22]. Given an integer and several sets where the sets may have some elements in common, the maximum coverage problem aims to select at most of these sets to cover the maximum number of elements. Furthermore, we need to discuss the existence of a solution that the MC problem is reducible to the RT L problem in polynomial time.
Given a directed evolving graph G, a group of users U, and the predicted snapshot graph from G, we reduce the MC problem to RT L with the following process: (1) For a given group U, we compute the influence users set of U as (U, ); (2) ∀ ∈ G\ , we create a set with the elements collected from the influenced users (U, ) − (U, ) while = ⊕ ; (3) We set the reconnecting edges of RT L as , which is the same as the input of . The above reduction can be done in polynomial time. Since the Maximum Coverage problem is NP-hard, so is the RT L problem. □ Theorem 3.2 (Influence Spread). The influence spread function (.) under the RT R problem is monotone and submodular.

SKETCH BASED GREEDY ALGORITHM
To answer the RT R query problem, we first predict the graph structure of the given evolving graph G at by using the link prediction method [50]. According to Theorem 3.2, the influence spread function of RT R is submodularity and monotonicity. Therefore, one possible solution of the RT L problem is to use the greedy approach to iteratively find out the most influential edge , in which reconnecting in predicted snapshot graph will maximize the influence spread of given users group U in (e.g., = ⊕ ). So far, the remaining challenge of RT R query is to evaluate the effect of a reconnected edge on the influence spread of U in .

Existing IM Approaches Analysis
As mentioned in [23], we can estimate the influence spread of given users by using the Monte Carlo simulation. Specifically, given users group U, we simulate the randomized diffusion process with U in for R times. Each time we count the number of active users after the diffusion ends, and then we take the average of these counts over the R times as the estimated number of influenced users of U. However, the Monte Carlo simulation method is much time-consuming and cannot be used in the large graph. Later on, Borgs et al. [3] proposed a Reverse Reachable Sketch-based method to the IM problem, named Reverse Influence Set (RIS) sampling, and the extended versions of the RIS method [33,34,40] were widely used to answer the IM problem as the state-of-the-art IM query methods. The Reverse Influence Set (RIS) sampling technique is a Reverse Reachable Sketch-based method to the IM problem. By reversing the influence diffusion direction and conducting reverse Monte Carlo sampling, RIS can significantly improve the theoretical run time bound of the IM problem.
Unfortunately, the RIS sampling method is not suitable for answering our RT R query. That is because the RIS sampling is designed to find the Top-most influential users in a graph, but our RT R query focuses on reconnecting several optimal edges to enhance a given user group's influence spread. In particular, the RIS sampling method transforms the IM problem to find the optimal seed set by generating 1 RR sets, while can cover most RR sets. The RR sets only contain the user's information while discarding the graph sketch (e.g., the edge's information). Therefore, if we use the RIS sampling to answer the RT R query, we have to recompute the RR sets for each edge insertion during the RT R query process, which is time-consuming and unrealistic in large graphs.

FI-Sketch based Greedy Algorithm
Facing the challenges mentioned above, we propose a sketch-based greedy (SBG) method to answer the RT R query. Precisely, we first set 3 as a sufficient number of generated sketch subgraphs in our SBG method to theoretically ensure the quality of the returned results for the RT R query (i.e., the details of how 3 should be set will further discuss in Section 4.3). Then, we use the FI-SKETCH to evaluate the effect of a new adding edge on the influence spread of a given users group U based on the 3 generated sketch subgraphs. Compared with the RIS approach, the graph structure information was contained in the generated 3 sketch subgraphs during the process of the FI-SKETCH approach (refer to Section 2.4), so that we do not need to recompute the sketches while the edges update.
The details of the SBG method are described in Algorithm 1. In the pre-computing phase (Lines 1-3), we predict the snapshot graph using the link prediction method [50], and then generate 3 random sketch graphs by removing each edge = ( , ) from with probability 1 − , . Besides, based on Definition 3.1, we initialize ∈ {G \ } as the candidate edges set of the RT R query. In the main body of SBG (Lines 4-6), we use the greedy method to iteratively find the number of optimal reconnecting edges. Specifically, in each iterative, we call the FI-SKETCH Function to find out the optimal edge from the candidate edge set and add into set , while reconnecting the selected edge can maximize the influence diffusion of given users group U. Meanwhile, given an edge , the FI-SKETCH Function returns back the influenced users evaluation results by using the Forward Influence Sketch method mentioned in Section 2.4 (Lines [8][9][10][11][12][13][14]. Finally, we return edges set as the result of RT R query (Line 7). Complexity. The time complexity of calling the FI-SKETCH function for each candidate edges is O ( 3 · | |), while the space complexity is O ( 3 · (| | + | |)). Hence, the time complexity and space complexity of SBG algorithm are O ( · | | · 3 · | |) and O ( 3 · (| | + | |)), respectively.

Theoretical Analysis of SBG
In this part, we will establish our theoretical claims for SBG. Specifically, we analyze how 3 should be set to ensure our SBG method returns near-optimal results to RT R query with high probability. Our analysis highly relies on the Chernoff bounds [19].
Let U be a group of users, be the selected reconnecting edges, R 2 be the number of generated sketch subgraphs in the SBG algorithm (Algorithm 1), and (U, ) be the total number of additional reached users by U in each sketch subgraph after reconnecting edges in . From [35], the expected value of ( U, ) R 2 equals the expected influence diffusion enhance by reconnecting edges of in . Then, we have the following lemma.
Proof. Each sketch subgraph in the SBG algorithm is generated by removing each edge with 1− ( ) probability. From [35], we can observe that the expected value of the average number of reached users to U in all sketch subgraphs is equal to the expected spread of U in . From the above relation of equality, we can easily deduce that [ Proof. We can prove Theorem 4.1 by tweaking the proof in Theorem 2.1 of [40]. Let be the probability of U can activate a fixed user after reconnecting edges in in . Based on Lemma 4.2, Then, we have Let = 2| | . Based on Lemma 4.1, we have Thus, Theorem 4.1 is proved. □ utilizing the greedy algorithm of maximum coverage problem [22], which produces a (1 − 1 ) approximation solution (mentioned in Theorem 3.1). Finally, by combining the above two approximation ration 2 and (1− 1 ), we can conclude the final approximation ration of our SBG method for solving RT R query problem is (1 − 1 − ) with at least 1 − | | − probability. □

Reducing # Candidate Edges
Since the SBG algorithm's time complexity is cost-prohibitive, which would hardly be used for dealing with the sizeable evolving graph. In this subsection, we present our optimization method by pruning the unnecessary potential edges in candidate edge set . The core idea behind this optimization strategy is to eliminate the edges in which will not have any benefit to expend the influence spread of given users group U while reconnecting it.
We use the symbol U to denote that can be reached by U. In order to reduce the size of , we present the below theorem to identify the quality reconnecting edge candidates (denote as ) from . Theorem 4.3 (Reachability). Given a directed snapshot graph and a users group U, if an edge = ( , ) is selected to reconnect, one of its related users (i.e., or ) requires to be reached by U in ; that is ∈ implies U or U in .
Proof. We prove the correctness of this theorem by contradiction. The intuition is that at least one pathway exists from a user to all of its influenced users in social networks. For the selected edge = ( , ), if both the user and are not reached by the users group U, then the pathway between U and does not exist. Therefore, reconnecting the edge does not bring any benefits to the expansion of influence spread starting from U, which contradicts with Definition 3.1. Thus, the theorem is proved. □   Figure 2 shows a snapshot graph with 10 nodes and 9 edges. The candidate edges set of RT R is = {( 3 , 4 ), ( 5 , 6 ), ( 6 , 10 )}. For a given user group U = { 1 }, the pruned candidate edge set would be = {( 5 , 6 ), ( 6 , 10 )} due to 6 U.
Based on Theorem 4.3, we present a BFS-based method for pruning the candidate edge set in graph with a given users group U. The core idea of the BFS-based algorithm is to traverse the graph starting from the nodes in U by performing breadth-first search In Algorithm 2, we outline the major steps of the BFS-based method for processing the pruning. Initially, each user in graph are marked a visiting status as FALSE (Line 2). Then, for the users in a given group U, we update its visiting status as TRUE (Lines 3-5). Further, we process a BFS search starting from root user ∈ U, and update the status of each visited users as TRUE (Lines 6-12). Next, based on Theorem 4.3, we reduce all candidate edges = ( , ) from while both and have the FALSE visited status (Lines 13-17), and finally, we return the pruned candidate edges set (Line 18). Complexity. Obviously, for a given group U, the time complexity of Algorithm 2 is O (| | + | | + | |), and the space complexity is O (| |). Furthermore, the occupied space by Algorithm 2 will be released after the pruned candidate edges is returned. For each RT R query with a new given users group U as input, we need to recall the BFS-based pruning method to reduce the size of candidate set with time cost O (| | + | | + | |), which is the main drawback of the BFS-based pruning method.

THE IMPROVEMENT ALGORITHM
Although the SBG algorithm and its optimization method can successfully answer the RT R query problem, it is still time-consuming to handle the sizeable social networks. To address this limitation, in this section, we propose an ordered sketch-based greedy algorithm, which can significantly reduce the number of edges influence probing at each iterative of RT R query process, so as to answer the RT R query more efficiently.

Algorithm Overview
Let G = { 0 , 1 , ..., −1 } be an evolving graph. We first use the temporal link prediction method [56] to predict the future snapshot of graph , and the potential reconnecting edges will be selected from candidate edges set = {G \ }. Before introducing the core idea of our Order-based SBG algorithm, we first briefly review using the SBG algorithm to answer the RT R query and analyze the bottleneck of the SBG algorithm.
For each given users group U, the SBG algorithm aims to find reconnecting edges by iteratively probing each edge in to find out the edge in which reconnecting will bring the maximum benefits to the influence spread of U. The time complexity of influence spread by reconnection of an edge is O ( 3 · | |), which is the bottleneck of the SBG algorithm.
To deal with the above limitation of the SBG method, we propose an Order-based SBG algorithm, which focuses on reducing the number of edges probing in each iteration by using our elaboratively designed two-step bounds approach together with the order-based probing strategy. Specifically, we first generate a label index (UBL) to store the first step upper bound of influence spread expansion for each candidate edge ∈ w.r.t 1 ( ) (in Section 5.2). Then, we generate the initial second-step upper bound ( 2 ) for (i.e., 2 . ) from 1 ( ) of the UBL index. Next, in the influence spread expansion estimation query processing of each given users group U and probing edge , we narrow the second-step upper bound of and update the 1 ( ) value of UBL index, while the narrowed second-step upper bound will be served the optimal edge finding in the following iterations (in Section 5.3). Finally, we order the candidate edges by their 2 values. The edge probing at the current iteration will be early terminated while the second upper bound of probing edge is less than the present influence spread expansion estimation value (in Section 5.4).

Upper Bound Label (UBL) Construction
This section introduces how to build the label index (UBL) for each candidate edge. The UBL index contains two parts, including (1) the 3 sketch subgraphs ; (2) the first-step bound 1 ( ) of each candidate edge and its updating status. The details of UBL construction procedure is shown in Algorithm 3.
From Section 2.4, we first generate 3 sketch subgraphs from the predicted snapshot graph that will be used for the future influence spread estimation (Line 2). Then, for each candidate edge in , we initialize its updating mark (i.e., ( )) as 0. Meanwhile, we compute the number of vertices in that can be reached from as the first step upper bound of , denoted as 1 ( ) (Lines 3 -6). Finally, we store the Labeling Scheme (L, ) for RT R query processing (Line 7). Complexity. The time complexity of sketch subgraphs generation is O ( 3 · | |), and the 1 labeling construction of all candidate edges in is (| | · | |). Therefore, the time complexity of UBL construction is O ( 3 · | |+| | · | |). Besides, the space complexity of UBL index construction is O ( 3 · (| | + | |) + | |), while storage sketch subgraphs has space complexity ( 3 · (| | + | |)) and generating 1 labeling of edges in has space complexity of O (| |).

Influence Spread Expanding Estimation
Here, we present the influence spread expansion estimation of given users group U and edge . Further, we also introduce the strategies of narrowing the two-step upper bounds of (i.e., 1 ( ) and 2 ( )) during the above estimation process.

End Function
The details of the influence spread expansion estimation are described in Algorithm 4. For a given users group U and edge = ( , ), the Sketch-Estimate Function aims to compute the incremental of U's influence spread while reconnecting edge in graph . It takes sketch subgraphs , query edge and group U, influenced marking array , two-step bound 1 and 2 , and returns the influence spread expansion value of to U. We initialize two variable and as 0 (Line 2). Then, an inner loop fetches the total number of the reached nodes for in each sketch subgraph ∈ but not be reached by U (i.e., update the value of 2 as / 3 , which is also the influence spread expansion value of (Line 12); we also update 1 ( ) and remark ( ) = 1 of L when the original mark L. ( ) = 0 (Line 13 -15). Finally, the influence spread expansion of is returned (Line 16). It is remarkable that with the increasing number of RT R queries for different given users group U, the more edges' first-step upper bound 1 will be narrowed, so as to the performance of the later RT R query with new users group will increase with no additional cost. Complexity. It is easy for us to derive that the time complexity and space complexity of Algorithm 4 are O ( 3 · | |) and O ( 3 · | |), respectively.
Example 5.1. Figure 3 shows a running example of our two step bounds generation. For a given graph in Figure 2, we first identify the candidate edges set = {( 3 , 5 ), ( 5 , 6 ), ( 6 , 10 )}. Then, we compute the first-step bound of each edge in (e.g., 1 ( 3 , 5 )) and set its initial flag as −1. During the process of each RT L query with different given users group U, we will prune the candidate edges set from to , and call the Sketch-Estimate Function (e.g., Algorithm 4) to estimate the influence spread expansion of each probing edge (e.g., 2 = ( 5 , 6 )) from . Meanwhile, during the above process, we get a byproduct of 2 , the second step upper bound 2 ( 2 ), which can be used to narrow the first upper bound of 2 (e.g., 1 ( 2 ) ← 2 ( 2 )). Once 1 ( 2 ) is updated, 2 's flag also needs to be changed to +1.

Order-based SBG for RT R Query Processing
In the previous parts of this section, we have overviewed the main idea of our order-based SBG algorithm. We also have introduced the details of two essential blocks of our Order-based SBG algorithm: (i) the UBL construction and (ii) the Sketch-Estimation Function. In the rest of this section, we will discuss the details of the Order-based SBG algorithm. The details of the Order-based SBG algorithm are described in Algorithm 5. It takes an integer , a users group U, the candidate edges , and UBL index (L, ) as inputs, and returns a set of optimal reconnecting edges that maximizes the influence spread of U. We initialize a set as empty, an empty Priority queue that will be used to store the 2 information of candidate edges related to U, and an array to mark whether a node can be reached by U or edges in at each sketch subgraphs (Line 1). Then, we reduce the candidate edges from by using Algorithm 2, and record the reduced candidate edges into set (Line 2). For each edge in , we get 's first-step upper bound 1 ( ) from UBL index, and set 1 ( ) as the initial second-step upper bound value of (i.e., 2 ( ) = L. 1 ( )), and then push ( , 2 ( )) into priority queue (Lines 3 -16). Next, we mark the nodes which are reached by U in each sketch subgraphs of (Lines 5 -7). Further, in each iteration, we probe the candidate edges in priority queue in order based on their 2 value, and then call Sketch-Estimation Function to compute the influence spread expansion of the probing edge , the edge probing in this iteration will be early terminated once the front edge from Q is less than the currently maximum influence spread expansion value (Line 8). After finding out the optimal edge , we update the mark of nodes reached by in each sketch subgraphs (Lines 13 -17). Finally, it returns the optimal reconnecting edge set having maximum influence spread expansion of U (Line 25). Complexity. The time complexity of Algorithm 5 is O (| | + 3 · | | + · | | · 3 · | |). Besides, the space complexity is O (| | +

EXPERIMENTAL EVALUATION
In this section, we present the experimental evaluation of our proposed approaches for the RT L queries: the sketch based greedy algorithm (SBG) in Section 4.2; the candidate edges pruning method to accelerate SBG (CE-SBG) in Section 4.4; and the Order-based SBG solution (O-SBG) in Section 5.4.

Experimental Setting
We implement the algorithms using Python 3.6 on Windows environment with 2.90GHz Intel Core i7-10700 CPU and 64GB RAM.
Baseline. To the best of our knowledge, no existing work investigates the RT R problem. To further validate, we use our SBG algorithm as the baseline algorithm to compare with CE-SBG and O-SBG. This is because the well-known RIS based IM methods [34,40] are hardly used in the RT R query (i.e., mentioned in Section 4.1). Meanwhile, our SBG algorithm is extended from the FI-sketch IM method (i.e., SG algorithm [10]), while the SG algorithm performs well within the existing IM efforts, which has been validated in the state-of-the-art IM benchmark study [1]. Datasets. We conduct the experiments using five publicly available datasets from the Large Network Dataset Collection 2 : eu-core, Col-legeMsg, mathoverflow, ask-ubuntu, and stack-overflow. The statistics of the datasets are shown in Table 2. We have averagely divided all datasets into graph snapshots (e.g., = ( , ), ∈ [1, ]), where is the node and is the edges appearing in the time period of in each dataset. Parameter Configuration. Table 3 presents the parameter settings. We consider four parameters in our experiments: the number of queries , the size of given users group |U|, reconnecting edges size , and the number of snapshots . Besides, the near future snapshot +1 is generated by using the recent link prediction method [50] In each experiment, if one parameter varies, we use the default values for the other parameters. Besides, we set 3 = 200, which is consistent with [1].

Efficiency Evaluation
We study the efficiency of the approaches for the RT L problem regarding running time under different parameter settings. Figure 4 shows the average running time of our proposed methods by varying between 1 to 40. The running time of the algorithms follows similar trends, where SBG consumes maximum time to process an RT R query. On average, O-SBG is 65 to 99 times faster than CE-SBG, and 90 to 167 times faster than SBG. Also, CE-SBG is about 3 to 11 times faster than SBG in different datasets when varies from 2 to 40. Notably, when is larger than 30, the SBG algorithm fails to return the result of the RT R query within one day. As expected, the running time of both three approaches significantly increases when is varied from 1 to 40. Besides, the growth of running time in O-SBG is much slower than the other two algorithms. This is because the probing candidate edges will increase in all three approaches when increases, and O-SBG has the smallest number of probing candidate edges among the three approaches (refer to Figure 5).

Varying Reconnecting Edges Set Size .
The number of probing candidate edges of SBG, CE-SBG, and O-SBG with varying are presented in Figure 5(a)-5(d). As can be seen, the probing candidate edges of O-SBG is much less than SBG and CE-SBG for all values of . For example, when = 20, the probing candidate edges of SBG, CE-SBG, and O-SBG in mathoverflow are 91, 850, 28, 588, and 547, respectively. Besides, the number of probing candidate edges increases in all three approaches with the increase of , and O-SBG probing the least number of candidate edges in all three approaches. This result has verified the above explanation     Figure 7 shows the running time of the approaches by varying the size of users group U from 1 to 8. The results show similar findings that O-SBG outperforms CE-SBG and SBG as it utilizes the two step bounds to significantly reduce the probing candidate edges. For example, O-SBG can reduce the running time by around 150 times and 31 times compared with SBG and CE-SBG respectively under different |U| settings on the mathoverflow dataset.

Varying Snapshot Size .
We compare the efficiency of our proposed algorithms by varying the graph snapshots size from 20 to 100. Figure 8 presents the running time with varied values of . The results show similar finding that O-SBG outperforms SBG and CE-SBG in all datasets. Besides, we notice a similar running time trend in the proposed three methods when varies. Note that the running time does not always keep the same correlation with the varies of . This is because the performance of all three proposed approaches highly depends on the graph structure, and the number of snapshots does not show a perceptible effect on the network structure.   Figure 9 reports the average running time of O-SBG on mathoverflow. As we can see, the running time of O-SBG scales linearly with the increase of .

Effectiveness Evaluation
In this experiment, we evaluate the number of expanding influence users produced by the RT L problem with different datasets and approaches in Figure 10 - Figure 12 by varying one parameter and setting the others as defaults. As can be seen, the average number of influenced users of RT R queries in dense graphs is significantly larger than in sparse graphs for all three approaches. Figure 10 shows the average number of influenced users of all three approaches O-SBG, CE-SBG, and SBG on four datasets with varying . For example, in Figure 10 = 986, temporal edges = 332, 334, average degree = 25.28), respectively. Similar pattern can also be found in Figure 11 - Figure 12 as more influenced users be returned in dense graphs than in sparse graphs. In addition, Figure 11 reports that the influenced users of all three approaches do not always keep the same correlation with the increases of U. Figure 12 shows that the number of influenced users by all three approaches significantly increases when changes from 1 to 40. For example, the numbers of influenced users by O-SBG, CE-SBG, and SBG when setting as 40 are 23 times, 11 times, and 15 times larger than setting as 1 in the mathoverflow dataset. From the above experimental results, we can conclude that reconnecting the top-relationship query is necessary to maximize the benefits of expanding the influenced users of a given group.

RELATED WORK 7.1 Influence Maximization
Influence maximization (IM) was first formulated by Domingos et al. [13] as an algorithmic problem in probabilistic methods. Later on, Kempe et al. [23] modeled IM as an algorithmic problem in 2003. As the IM problem is NP-hard, all existing methods focus on approximate solutions, and a keystone of these algorithmic IM studies is the greedy framework. The existing IM algorithms can be categorized into three categories: simulation-based, proxy-based, and sketch-based. Simulation-based approaches. The key idea of these approaches is to estimate the influence spread ( ) of given users set by using the Monte Carlo (MC) simulations of the diffusion process [23,27,54]. Specifically, for a given users set , the simulation-based approaches simulate the randomized diffusion process with for times. Each time they count the number of active users after the diffusion ends, and then take the average of these counts over the times. The accuracy of these approaches is positively associated with the number of . The simulation-based approaches have the advantage of diffusion model generality, and these approaches can be incorporated into any classical influence diffusion model. However, the time complexity of these approaches are cost-prohibitive, which would hardly be used for dealing with sizeable networks. Proxy-based approaches. Instead of running heavy MC simulation, the proxy-based approaches estimate the influence spread of given users by using the proxy models. Intuitively, there are two branches of the proxy-based approaches, including (1) Estimate the influence spread of given users by transforming it to easier problems (e.g., Degree and PageRank) [6,15]; and (2) Simplify the typical diffusion model (e.g., IC model) to a deterministic model (e.g., MIA model) [6] or restrict the influence propagation range of given users under the typical diffusion model to the local subgraph [16], to precisely compute the influence spread of given users. Compared with the simulation-based approach, a proxy-based approach offers significant performance improvements but lacks theoretical guarantees. Sketch-based approaches. To avoid running heavy MC simulations and reserve the theoretical guarantee, the sketch-based approaches [3,9,10,33,35,40] pre-compute a number of sketches Q   under a specific diffusion model, and then speed up the influence evaluation based on the constructed sketches. Compared with the simulation-based approaches, the sketch-based approaches have a lower time complexity under a theoretical guarantee. Unfortunately, the sketch-based approaches are not generic to all diffusion models because the generated sketches of the sketch-based approaches are relay on the underlying diffusion models.

Link Prediction
Link prediction (LP) is an important network-related problem, first proposed by Liben-Nowell et al. [31]. The LP problem aims to infer the existence of new links or still unknown interactions between pairs of nodes based on the currently observed links. After decades study, a series of LP methods were proposed, including: similarity approaches [18,55], probabilistic approaches [12,44], hybrid approaches [46,52], and deep learning approaches [38,49,50].
In this paper, we use the SEAL method [49,50] to predict the structure of the near future (i.e., time point ) snapshot graph (i.e., ) for a given evolving graph. Furthermore, for each given users group U, our RT R query problem aims to reconnect a set of edges in to maximize the number of influenced users of U in , which is quite distinct from all existing IM works.

CONCLUSION
In this paper, we studied the problem of Reconnecting Top-Relationships (RT R), which aims to find previous existing relationships but being estranged subsequently, such that reconnecting these relationships would maximize the influence spread of given users group. We have shown that the RT L query problem is NP-hard. We developed a FI-Sketch based greedy (SBG) algorithm to solve this problem. We further devised an edge reducing method to prune the candidate edges that the given users' group cannot reach. Moreover, an order-based SBG method has been designed by utilizing the submodular characteristic of the RT L query and two well-designed upper bounds. Lastly, the extensive performance evaluations on real datasets also revealed the practical efficiency and effectiveness of our proposed method. In the future, we will focus on developing more efficient approaches to deal with the RT R queries in hyper scale networks.