Fast Skyline Community Search in Multi-Valued Networks

We consider the case that nodes have two attributes, denoted as $(A^1,A^2)$ . For a node $u$ , let $(a_u^1,a_u^2)$ denote the attribute values of $u$ . For a community $C$ , its CI is denoted as $(f_1,f_2)$ . Basically we need to figure out all $(f_1,f_2)$ values that are MCI, based on which all skyline communities can be found.

Basically, we need to filter the $k$ -cores to finally find skyline communities. The algorithm proposed in Ref. [ 7 ] relies on the assumption that the values of nodes on each particular dimension are all different, which admits that the algorithm just considers the $k$ -cores containing some specific nodes. However, this idea does not work anymore when multiple nodes may have the same value on a particular dimension, as it cannot determine a unique node by a fixed value in a dimension. Hence, we propose a manner relying on MCIs to filtering $k$ -cores.

Specifically, Algorithm 1 is first invoked to compute the largest CI on the $A^2$ dimension, denoted by $f_2^{*}$ . Then, all nodes $v$ with $a_v^2<f_2^{*}$ are deleted from the graph. Notice that instead of actually deleting these nodes from the graph $G$ , they are just removed temporarily so as to find out the communities whose CI on the $A^2$ dimension equals $f_2^{*}$ . After that, Algorithm 1 is invoked again to find the largest value of nodes on the first dimension in the remaining graph, denoted as ${\tilde{f}}_1$ . It is easy to check that $({\tilde{f}}_1,f_2^{*})$ is an MCI.

Once we obtain the MCI of $({\tilde{f}}_1,f_2^{*})$ , we can immediately compute the corresponding communities. But how can we efficiently find other skyline communities? Notice that the value of $f_2$ in above MCI we have found is the largest on the $A^2$ dimension, so we have to increase $f_1$ to find other MCIs. Based on this idea, the nodes $v$ with $a_v^1⩽{\tilde{f}}_1$ can be deleted from $G$ , as communities with these nodes are dominated by the community we have found. In the remaining graph, we iteratively use the same method to find the MCIs and corresponding skyline communities till $f_2=0$ . The detailed algorithm is given in Algorithm 2. In Algorithm 2, $\mathrm{dlist}$ is used to store current $(f_2,f_1)$ value. Since the algorithm computes $f_2$ first and $f_1$ later, we will also generate $\mathrm{dlist}$ in this order. Besides, $\mathrm{fdf1}$ is a global variable that holds all the MCIs we have found. Initially, $\mathrm{dlist}$ and $\mathrm{fdf1}$ are empty.

Theorem 2 In the case of $d=2$ , Algorithm 2 can compute all communities with time complexity of $O(l(m+n))$ , where $l$ is the maximum of different dimension values on every dimension.

Proof In Algorithm 2, MaxCI is first invoked to compute the maximum value on the $A^2$ dimension, which takes $O(n+m)$ time. After that, all MCIs and corresponding communities are iteratively calculated. The total number of iterations is upper bounded by $l$ , and each iteration takes $O(n+m)$ . Combining all together, the time complexity of the algorithm can be derived.

We consider the case that nodes have two attributes, denoted as $(A^1,A^2)$ . For a node $u$ , let $(a_u^1,a_u^2)$ denote the attribute values of $u$ . For a community $C$ , its CI is denoted as $(f_1,f_2)$ . Basically we need to figure out all $(f_1,f_2)$ values that are MCI, based on which all skyline communities can be found.

Basically, we need to filter the $k$ -cores to finally find skyline communities. The algorithm proposed in Ref. [ 7 ] relies on the assumption that the values of nodes on each particular dimension are all different, which admits that the algorithm just considers the $k$ -cores containing some specific nodes. However, this idea does not work anymore when multiple nodes may have the same value on a particular dimension, as it cannot determine a unique node by a fixed value in a dimension. Hence, we propose a manner relying on MCIs to filtering $k$ -cores.

Specifically, Algorithm 1 is first invoked to compute the largest CI on the $A^2$ dimension, denoted by $f_2^{*}$ . Then, all nodes $v$ with $a_v^2<f_2^{*}$ are deleted from the graph. Notice that instead of actually deleting these nodes from the graph $G$ , they are just removed temporarily so as to find out the communities whose CI on the $A^2$ dimension equals $f_2^{*}$ . After that, Algorithm 1 is invoked again to find the largest value of nodes on the first dimension in the remaining graph, denoted as ${\tilde{f}}_1$ . It is easy to check that $({\tilde{f}}_1,f_2^{*})$ is an MCI.

Once we obtain the MCI of $({\tilde{f}}_1,f_2^{*})$ , we can immediately compute the corresponding communities. But how can we efficiently find other skyline communities? Notice that the value of $f_2$ in above MCI we have found is the largest on the $A^2$ dimension, so we have to increase $f_1$ to find other MCIs. Based on this idea, the nodes $v$ with $a_v^1⩽{\tilde{f}}_1$ can be deleted from $G$ , as communities with these nodes are dominated by the community we have found. In the remaining graph, we iteratively use the same method to find the MCIs and corresponding skyline communities till $f_2=0$ . The detailed algorithm is given in Algorithm 2. In Algorithm 2, $\mathrm{dlist}$ is used to store current $(f_2,f_1)$ value. Since the algorithm computes $f_2$ first and $f_1$ later, we will also generate $\mathrm{dlist}$ in this order. Besides, $\mathrm{fdf1}$ is a global variable that holds all the MCIs we have found. Initially, $\mathrm{dlist}$ and $\mathrm{fdf1}$ are empty.

Theorem 2 In the case of $d=2$ , Algorithm 2 can compute all communities with time complexity of $O(l(m+n))$ , where $l$ is the maximum of different dimension values on every dimension.

Proof In Algorithm 2, MaxCI is first invoked to compute the maximum value on the $A^2$ dimension, which takes $O(n+m)$ time. After that, all MCIs and corresponding communities are iteratively calculated. The total number of iterations is upper bounded by $l$ , and each iteration takes $O(n+m)$ . Combining all together, the time complexity of the algorithm can be derived.

We consider the case that nodes have two attributes, denoted as $(A^1,A^2)$ . For a node $u$ , let $(a_u^1,a_u^2)$ denote the attribute values of $u$ . For a community $C$ , its CI is denoted as $(f_1,f_2)$ . Basically we need to figure out all $(f_1,f_2)$ values that are MCI, based on which all skyline communities can be found.

Basically, we need to filter the $k$ -cores to finally find skyline communities. The algorithm proposed in Ref. [ 7 ] relies on the assumption that the values of nodes on each particular dimension are all different, which admits that the algorithm just considers the $k$ -cores containing some specific nodes. However, this idea does not work anymore when multiple nodes may have the same value on a particular dimension, as it cannot determine a unique node by a fixed value in a dimension. Hence, we propose a manner relying on MCIs to filtering $k$ -cores.

Specifically, Algorithm 1 is first invoked to compute the largest CI on the $A^2$ dimension, denoted by $f_2^{*}$ . Then, all nodes $v$ with $a_v^2<f_2^{*}$ are deleted from the graph. Notice that instead of actually deleting these nodes from the graph $G$ , they are just removed temporarily so as to find out the communities whose CI on the $A^2$ dimension equals $f_2^{*}$ . After that, Algorithm 1 is invoked again to find the largest value of nodes on the first dimension in the remaining graph, denoted as ${\tilde{f}}_1$ . It is easy to check that $({\tilde{f}}_1,f_2^{*})$ is an MCI.

Once we obtain the MCI of $({\tilde{f}}_1,f_2^{*})$ , we can immediately compute the corresponding communities. But how can we efficiently find other skyline communities? Notice that the value of $f_2$ in above MCI we have found is the largest on the $A^2$ dimension, so we have to increase $f_1$ to find other MCIs. Based on this idea, the nodes $v$ with $a_v^1⩽{\tilde{f}}_1$ can be deleted from $G$ , as communities with these nodes are dominated by the community we have found. In the remaining graph, we iteratively use the same method to find the MCIs and corresponding skyline communities till $f_2=0$ . The detailed algorithm is given in Algorithm 2. In Algorithm 2, $\mathrm{dlist}$ is used to store current $(f_2,f_1)$ value. Since the algorithm computes $f_2$ first and $f_1$ later, we will also generate $\mathrm{dlist}$ in this order. Besides, $\mathrm{fdf1}$ is a global variable that holds all the MCIs we have found. Initially, $\mathrm{dlist}$ and $\mathrm{fdf1}$ are empty.

Theorem 2 In the case of $d=2$ , Algorithm 2 can compute all communities with time complexity of $O(l(m+n))$ , where $l$ is the maximum of different dimension values on every dimension.

Proof In Algorithm 2, MaxCI is first invoked to compute the maximum value on the $A^2$ dimension, which takes $O(n+m)$ time. After that, all MCIs and corresponding communities are iteratively calculated. The total number of iterations is upper bounded by $l$ , and each iteration takes $O(n+m)$ . Combining all together, the time complexity of the algorithm can be derived.

In the scenario of $d=3$ , the method of computing the MCIs used in the case of $d=2$ , i.e., determining the largest value in one dimension and then going through the values on the other dimension, is unavailable any more. This is because in the case of $d⩾3$ , after computing the maximal value in one dimension, it is hard to determine the remaining values of a skyline community on other dimensions.

Our algorithm uses a similar dimension reduction idea as that in the algorithm given in Ref. [ 7 ]. But here we need to implement the algorithm based on the MCIs, rather than some specific nodes. Basically, we first fix one dimension and derive all possible values on the dimension. Then, for each possible value on the fixed dimension, the algorithm invokes itself with dimensional parameter $d-1$ to compute the $(d-1)$ -dimensional skyline communities. By checking whether the CI of these skyline communities is MCI, all $d$ -dimensional skyline communities are finally found.

The detailed implementation of our algorithm is shown in Algorithm 3. Similar to Algorithm 2, the MaxCI method is first invoked to calculate the maximum $f$ value of maximal $k$ -cores on the $d$ -th dimension, denoted by $f^{*}$ (Line 6). Let $F$ denote the set of all possible values on the $d$ -th dimension. For each value $f\in F$ with $f⩽f^{*}$ , the algorithm invokes itself to compute $(d-1)$ -dimension skyline communities, after deleting all nodes with $a_v^d<f$ (Lines 7-14). When the dimension is reduced to 2, Algorithm 2 is invoked to compute $2$ -dimensional skylines (Lines 2 and 3). After determining the value of each dimension in the above procedure, it is then checked whether the CI composed by these values is maximal. Once an MCI is determined, its corresponding skyline communities are then found.

Theorem 3 For $d⩾3$ , Algorithm 3 can find all skyline communities, and the time complexity is $O(l^{d-2}(l(m+n)))$ .

Proof For each CI generated in the algorithm, algorithm MICS will determine whether it is dominated by previous MCIs, and all possible combinations of $(f_1,\mathrm{\dots },f_d)$ have been considered, so it is ensured that all MCIs have been found. According to each MCI, corresponding skyline communities are computed simultaneously. Hence, all skyline communities are finally found. We next discuss the time complexity of algorithm MICS.

In each dimension reduction process, the algorithm with a smaller dimension parameter is invoked for at most $l$ times, and in general $l\ll n$ . When $d$ is reduced to 2, Algorithm 2 is invoked, which takes $O(l(m+n))$ time. Hence, the total time consumed is upper bounded by $O(l^{d-2}(l(m+n)))$ .

As shown in Theorem 3, though Algorithm 3 can perfectly solve the skyline community search problem, its time complexity is unacceptable, which increases exponentially with the increase of the number of dimensions. Hence, we subsequently present an algorithm that can compute important skyline communities, while significantly reduce the time complexity, by considering only a fixed number of dimensions when computing the skyline communities.