A Multi-granularity Decomposition Mechanism of Complex Tasks Based on Density Peaks

Firstly, for initial subtask centers set, it consists of the latent core nodes which can organize other non-core nodes to be a small subtask entirety. Besides, what calls for special attention is that the initial subtask centers set is not the final subtask centers set. For DPC algorithm, in the decision graph, there is some remarkable information for choosing the subtask centers set. For nodes set $T$ , calculating the value $ord\gamma =\rho \times \delta$ and descending ${\gamma }_i$ , which is shown in Table 3 . The nodes more closer to $ord{\gamma }_i$ would more likely to be the centers, because they possess the criterion of higher local density and relatively far distance according to DPC algorithm. Considering the problem of omitting any center, we select advisable and redundant center nodes from $ord{\gamma }_i$ , as the initial subtask centers set $CT$ .

After choosing advisable and redundant center tasks, the center tasks with their oriented subtask sets can be clearly observed from the global tasks leading tree. The oriented subtask nodes set $SC$ can be obtained by traversing the nodes of subtask centers set in the global tasks leading tree.

(5) $$SC(i)=\{t\in T|Nneigh(t)==CT(i),$$ $$i\in (1,sizeof(CT))\}$$

We assume that the subtask nodes set can split from the global task leading tree. Computing the similarity between $SC$ and $T-SC$ , if their similarity is less than the user-specified threshold $thres$ which is set according to the actual situation, it means $SC$ is not close or interconnected with the initial tasks $T$ . And it illustrates that $SC$ satisfies the condition to be an autocephalous subtask set. Therefore, by splitting the global tasks leading tree, several small and isolated subtrees would be generated. On the basis of splitting process, the solving space of the coarse granular layer will be segregated and form a solving space with fine granular layer which is composed by a series of polybasic and independent subtask sets. If the small subtask entireties have been processed altogether, the original complex task would be answered by synthesizing the answers of subtask entireties.

There are many algorithms to measure the similarity between objects, such as Euclidean metric, Cosine, and Jaccard in vector space model. We select the similarity measure method in Ref. [ 27 ], which is based on graph partitioning theory and fully considers relative interconnectivity and closeness, thereby manifesting great results in clustering.

Thus, the relative interconnectivity $RI$ between $SC$ and $T-SC$ is

(6) $$RI(SC,T-SC)=\frac{2\times |EC(SC,T-SC)|}{|EC\left(SC\right)|+|EC(T-SC)|}$$

where $EC(SC,T-SC)$ denotes the absolute interconnectivity between $SC$ and $T-SC$ and represents the total weights of the edges that straddle the nodes in $SC$ and $T-SC$ . $EC(SC)$ and $EC(T-SC)$ represent the sum weight of the edges in $SC$ and $T-SC$ , respectively.

The relative closeness $RC$ between $SC$ and $T-SC$ is

(7) $$RC(SC,T-SC)=\frac{\bar{S}EC(SC,T-SC)}{X_1\bar{S}EC(SC)+X_2\bar{S}EC(T-SC)}$$

and $X_1=\frac{\left|\begin{array}{c}\hfill SC\hfill \end{array}\right|}{\left|\begin{array}{c}\hfill SC\hfill \end{array}\right|+\left|\begin{array}{c}\hfill T-SC\hfill \end{array}\right|},X_2=\frac{\left|\begin{array}{c}\hfill T-SC\hfill \end{array}\right|}{\left|\begin{array}{c}\hfill SC\hfill \end{array}\right|+\left|\begin{array}{c}\hfill T-SC\hfill \end{array}\right|}$ . where $RC$ is the normalization of $RI$ . $\bar{S}EC(SC,T-SC)$ is the average weight of the edges that connect nodes between $SC$ and $T-SC$ . $\bar{S}EC(SC)$ and $\bar{S}EC(T-SC)$ denote the average weights of the edges that pertain to the min-cut bisector of $SC$ and $T-SC$ , respectively. Terms $|SC|$ and $|T-SC|$ are the numbers of nodes in $SC$ and $T-SC$ , respectively.

The similarity of $SC$ and $T-SC$ is measured by

(8) $$Similarity(SC,T-SC)=RI(SC,T-SC)\times$$ $$RC{(SC,T-SC)}^{\alpha }$$

where the user-specified parameter $\alpha$ is to control the relative importance between $RI$ and $RC$ . If $\alpha =1$ , it means that relative interconnectivity and closeness have the same importance.

By calculating the similarities of task subsets generated by $CT$ , we set a user-specific threshold $thres$ to control the progress of separating the initial coarse granular layer into fine granular layers. Here, we formalize some notions and rules for optimizing grain layer of solving spaces.

Definition 1 (Final tasks center set) Given a task $T$ , a redundant center task set denoted by $CT$ , $SC(i)$ is the subtask set of $T$ . For each node of $CT$ to calculate the $Similarity(i)=Similarity(SC(i),$ $T-SC(i))$ , select the nodes where $Similarity(i)<thres$ , and then, pop up the node which occupies maximum $\left|Similarity(i)-thres\right|$ to belong to the final tasks center set $FCT$ . When there is no node in $CT$ that satisfies the condition $Similarity<thres$ , the process of popping up center node is to terminate.

Definition 2 (Granulating rule) Within Definition 1, for each granulating operation, if there is a node popped up, granulate from on top coarse grain layer to under fine grain layer; granulation is to be terminated when center popping terminates.

In Definition 1, the paramount idea is that for each granulation the most likely center of subtask will be popped up, as conforms to the ideas of priority of majority. For every processing of popping, it is the processing of task decomposition; thus, we can obtain an accurate center of subtask. Via the method in Definition 2, we get a precise fine grain layer of solving space, since the terminal optimal decomposition of task has been captured. Our method can pop up the potential subtask centers and automatically generate the optimal fine granularity task solving space where we can decompose the complex task into undemanding subtask sets.

In Table 3 , $ord\gamma$ descends from $\gamma =\rho \times \delta$ . As we mentioned in Algorithm 3.2, we select the first to sixth nodes in $ord\gamma$ as advisable and redundant centers, so $CT=\{46,15,14,38,34,52\}$ . According to Definition 1 and Definition 2, we explore the final optimal task solving space of Dolphin social network. We set $thres=0.5$ , because if the Similarity between two communities is less than $0.5$ , it means that they are less connected to each other, so we consider that segregating the two communities is meaningful and ponderable.

According to Definition 1, for the first round shown in Table 4 , node $14$ is the most likely center of a community. Node $14$ and its child nodes should be split from the global leading tree, and then, the popped node $14$ should be removed from redundant $CT$ to $FCT$ . Next, consulting with Definition 2, we can granulate the initial coarse granular layer to a particular fine granular layer, which is shown in Figs. 4a and 4b . After the first popping, the terminal condition has not been triggered, so we continue executing the popping process until the terminal condition takes effect.

10.26599/BDMA.2018.9020023.F004 Fig. 4(a) Global leading tree structure of Dolphin network; (b) Progress of the first granulation, where node 14 is one of the community center, so the tree splits two sub trees, and they are constituted as a fine granularity task solving layer; (c) Granulating process triggered by center node 52, and they form a fine granular solving layer with three subtask sets.

In the second process shown in Table 5 , we can see that the node $52$ is popped up as the second latent community center, and an operation like first popping process is repeated until the terminal condition occurs. The granulating progress is presented in Figs. 4b and 4c .

In the third process shown in Table 6 , the terminal condition has been triggered automatically, because there is no node whose similarity is less than threshold.

In the Dolphin network, we select the second solving space to reveal the communities detected by our method. Compared to the real structure of Dolphin network, the results obtained by method MrGDM can ultimately conform to real communities, this proves that the MrGDM is practicable and meaningful, and can provide decent validity simultaneously. Figure 5 shows MrGDM results.

10.26599/BDMA.2018.9020023.F005 Fig. 5The structure of Dolphin network by MrGDM.