{'fraction_non_alphanumeric': 0.02711434523989251, 'fraction_numerical': 0.00821280835774027, 'mean_word_length': 5.037185563251914, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Enhance Ambiguous Community Structure via Multi-strategy Community Related Link Prediction Method with Evolutionary Process

Most real-world networks suffer from incompleteness or incorrectness, which is an inherent attribute to real-world datasets. As a consequence, those downstream machine learning tasks in complex network like community detection methods may yield less satisfactory results, i.e., a proper preprocessing measure is required here. To address this issue, in this paper, we design a new community attribute based link prediction strategy HAP and propose a two-step community enhancement algorithm with automatic evolution process based on HAP. This paper aims at providing a community enhancement measure through adding links to clarify ambiguous community structures. The HAP method takes the neighbourhood uncertainty and Shannon entropy to identify boundary nodes, and establishes links by considering the nodes' community attributes and community size at the same time. The experimental results on twelve real-world datasets with ground truth community indicate that the proposed link prediction method outperforms other baseline methods and the enhancement of community follows the expected evolution process.

contains the traditional graph partitioning methods like Kernighan-Lin algorithm [9] and it's extended version by Suaris et al. [10]. The second category adopts the hierarchical clustering, represented by the GN algorithm [6] and the FN algorithm [11]. The third category is the modularity based methods, which convert the clustering process into optimising modularity measures [5], [12], [13]. The fourth one contains the spectral clustering algorithms since the eigenvectors of network Laplacian matrices have several desirable properties related to community structure [14], [15], [16]. The last category is the dynamic methods, in which the spin models [17] and random walks [18] are often used.
However, most real-world datasets are severely incomplete [8], e.g., in online social networks like Facebook (currently renamed as Meta), Twitter and Sina, only part of global social information could be collected; in gene interaction networks, links among genes are usually measured by costly experiments. The prevalent imperfections on realworld network datasets might lead to incorrect community detection outcomes, so community enhancement methods are critical.
Researches have been conducted to fix impaired network systems by predicting which node pairs are more likely to establish links, also known as the link prediction methods [19], [20], [21], [22], [23], [24], [25]. However, to the best of our knowledge, researches on the topic of community enhancement by link prediction have been rarely discussed. Link predcition could be regarded as a data preprocssing procedure, which has played a key role in the practice of machine learning models [26], [27]. Therefore, it is natural to assume that the link prediction methods could have significant function and play a major role in community enhancement task.
Moreover methods: • Most methods do not take the evolution of network structure into consideration. Most experiments are conducted on single iteration or snapshot, such as the EdgeBoost [28] algorithm, in which the long term numerical stability is not discussed and only twohop neighbours are concerned.
• Most methods treat the community detection output as the ground truth result. However, as aforementioned, due to the imperfection of real-world data, clustering results are usually flawed, which means adjustments are required in link prediction algorithms to fix the results.
• Most methods only consider single strategy. However, applying different strategies simultaneously might gain notable improvement. For example, In graph representation learning, the IDGNN by Leskovec et al. [29] successfully achieved expressive power over 1-WL test [30] by applying two activation functions at the same time.
In this paper, we design a harmony-based aggregation preferred (HAP) link prediction method and propose a community enhancement algorithm based on this strategy. Our method comprises two distinct procedures. At the first stage it will suture fractured communities into a complete one, while the repaired communities will get enhanced at stage two. The diagram of such procedure is presented in figure 1. Experimental results on real-world datasets with ground truth community information show that our method achieves better performance than baseline methods in most cases. The main contributions of our work are: • We design a new link prediction strategy HAP for community enhancement task. Our HAP method does not require any prior knowledge about the ground truth community such as the number of communities.

•
The HAP method could be applied as a plug-in module in preprocessing procedure. It could be complementary to arbitrary community detection algorithms easily.
• Using Shannon Entropy, the definitions of consistency and harmony perform practical potential in community related problems or situations where nodes have attributes and POIs.
The remainder of this paper is organized as follows. Sect 2 presents related research work. Next, Sect 3 provides formal definition of community detection problem and illustrates the details of our method including the inductive biases. Furthermore, Sect 4 shows the experimental results and comparison with other baseline models. Finally Sect 5 gives the conclusion and future work.

RELATED WORK
Both link prediction and community detection are of great significance in network analysis since both of them provide network topology information from various perspectives.
For future references, three well-known community detection algorithms are introduced here: • Louvain [13]: It is a heuristic method based on modularity optimization. This algorithm first assigns different community labels to all nodes then optimizes the modularity by aggregating those separate communities.
• Infomap [31]: This method uses the probability flow of random walks on a network as a proxy for information flows in the real system. It is an information based approach capable in revealing community structure in weighted and directed networks.
• Label Propagation (LPA) [18]: The major advantage of this algorithm is that it has a near linear time complexity. LPA method solely uses the network structure as its information with each node adopting the label that most of its neighbours currently have at every iteration step.
Besides, several community detection algorithms were proposed based on the altering of network topology structure. Zhang et al. [32] designed an enhanced semisupervised learning framework for community detection, which required prior knowledge about nodes. Yang et al. [33] considered which prior information is critical for performance improvement and proposed an active link selection framework. Su et al. [34] proposed CSE method based on central and boundary node identification for community enhancement, which successfully removed the limitation of prior knowledge about nodes. Zhou et al. [35] proposed genetic algorithm and similarity ensemble based community enhancement methods to explore the robustness under adversarial attack.
In link prediction oriented problem, the community detecting results could be regarded as a global attribute to provide extra information for link prediction algorithms. Soundarajan and Hopcroft [36] rewrote the classic CN index and RA index with community information and the experimental results showed improvement. Rebaza and Lopes [37] took intra-cluster and inter-cluster into consideration and proposed WIC measure, which can be extended on directed and asymmetric large-scale networks [38]. Ai et al. [39] presented a link prediction method for personalized recommendation circumstance based on complex network modelling and community detection results.
Meanwhile, link prediction methods can be used to enhance ambiguous community structure. Yang et al. [40] proposed a conditional model for link prediction and a discriminative model for content analysis. Chen et al. [41] tested three traditional link prediction methods for enhancing community structure. Bacco et al. [42] proposed a generative model for multilayer network with interdependence among its layers. Jiang et al. [43] designed a strategy based on node centralities to establish clear boundaries among communities. Burgess et al. [28] proposed EdgeBoost structure and explored the improvement of community detection performance of three link prediction algorithms with six community detection methods.

METHODS
In this section, we explain the proposed community enhancement algorithm in detail. The key component of the proposed enhancement algorithm is the HAP link prediction method, based on which the inductive biases and the intuitions will be illustrated. Firstly we will formally define the problem and all the symbols used in this paper.

Problem and Definitions
Every complex network system can be presented as an ordered tuple G = (V, E), where V is the set of nodes and E ⊆ V × V represents the edge set of network G [44]. In this paper we mainly concern about undirected graph, i.e., In addition, for network with community attributes, each node has its clustering label from ground truth knowledge C G or by applying community detection algorithms C A . In a network with K clusters, C = {C 1 , C 2 , · · · , C K } denotes the set of clustering labels. We consider both C G and C A as a function that satisfying C G , C A : V → C, namely ∀v ∈ V , it has its ground truth community attribute C G (v) ∈ C and algorithm result C A (v) ∈ C. Furthermore, C G (v) does not necessarily equal to C A (v).
N Ci stands for the number of nodes with the community attribute C i . CM is the connection matrix satisfying CM ∈ Z K×K . We let CM (i, j) be the number of edges between cluster C i and C j .
For future reference, the definition of revising edges is illustrated here. Given the ground truth community C G and algorithm's output To clarify, revising edges might not exist in some networks. At the same time we provide the definition of reinforcing edges:

Inductive Biases
It is worth noticing that in most cases, community detection methods will yield a larger number of clusters on both real world and synthesized networks.  Here we present the results of three community detection algorithms on nine real-world network systems in figure 2. Notice the difference in cluster numbers between ground truth knowledge and clustering results. Except Louvain method on Eurosis network, community detection methods output larger number of communities than ground truth. Especially in Cora OS dataset, the results of LPA and Infomap are 25 times larger than the actual instance number. The experimental results of those community detection methods on LFR benchmark graphs yields higher number of community is referred to [28]. All real-world datasets mentioned here will be formally introduced in section 4.
Furthermore, in most cases the emergence of extra clusters comes from the fracture of complete ground truth communities. For example, demonstrated in figure 3, the larger ground truth community in dolphins network gets fragmented into four smaller communities by the Infomap method. If the link prediction method could make connections among different parts of fractured subcommunities, community detection methods would achieve better performance by recognising and merging those subcommunities into a complete one.
If we could adjust the network topology structure by connecting nonexistent revising edges, the community detection algorithms would get a higher likelihood to recognize the ground truth community of network.
Moreover, since the proposed method is designed to make connections among fractured subcommunities, it has the tendency to form links between small community and large community. That is to say, if the size of community in the complex network has great difference, the link prediction method is risky to dissipate the small clusters.
In conclusion, the inductive biases in this paper are listed as follow • The outputs of community detection algorithms are highly likely to be incorrect and contain more clusters than actual case because detection methods tend to split large community into smaller ones.

•
The connecting of revising edges enhances the ambiguous community structure, which could help the downstream community detection algorithms preform better.

•
The sizes (number of nodes) of ground truth communities in a complex network are in similar scales.

Algorithm Skeleton
It is commonly accepted that ambiguous community structure is challenging for community detection studies due to the subtle difference between inter-edges and intra-edges [34]. The leading thought of the HAP link prediction method is to add links among fractured components of a complete community, thus turning misunderstood inter-edges into affirmative intra-edges.
As a community attribute related unsupervised link prediction method, the HAP method requires a community detection algorithm to trigger the community enhancement procedure since no prior knowledge about the ground truth community is available.
To be specific, the proposed community structure enhancement method contains three main iterating processes: 1) community detection; 2) central and boundary nodes recognition; 3) adding links. The community detection process will not be discussed here since it is given by the users.

Central Nodes Recognition
In order to achieve the goal of community enhancement, the HAP link prediction method will recognise central and boundary nodes while simultaneously adds links to the network. The proposed community enhancement method has an evolutionary process which will be explained in short notice.
When detecting the central and boundary nodes, most methods use centrality measure to define whether nodes are on the edge of community or not [34] [35]. Such centrality measure can be defined through average distance between intra-community nodes, which can be regarded as geometric distance centrality. Other methods, such as calculating the fraction of neighbour nodes that have the same community attributes, could be regarded as the probability of one-step random walk ending within the community.
These two measures are both successful in identifying boundary nodes. However, distance based centrality measure will bring unwanted calculation complexity. Meanwhile, nodes with large degree have a higher likelihood to yield smaller average distance. Also the definition of boundary node usually does not consider the node's neighbours with different community attributes.
The fraction of connection based method has less computation complexity and takes the neighbour nodes' community attributes into consideration. However, the linear expression in fraction of connection might not utilize the neighbourhood information fully since communities are usually treated without difference. Take figure 4a as an example. In [34], the centrality score of a node is defined as: where the numerator stands for the number of nodes with the same community attribute while the denominator is the degree of node u. So we can easily calculate that for the central node in figure 4a its centrality score equals to 3/7. If we alter the neighbour nodes' community attribute, the shortage of such centrality measure will be exposed. As shown in figure 4b. It can be seen that in figure 4b, the centrality score of the central blue node remains 3/7.
In other word, this centrality function fails to express the difference between figure 4a and 4b. Thus we should take the neighbour nodes' community attributes into deeper consideration.
There is no doubt that the most useful and easily accessible information for the centrality score is the neighbourhood of nodes. Furthermore, for node x, all its neighbour nodes Γ(x) should contain the community attribute information.
Here we define the neighbourhood community enumeration (NCE) of node x, given the community mapping function Such as in figure 4a, the central node's NCE is < 1, 1, 1, 2, 2, 3, 3 > (1, 2 and 3 stand for blue, green and red community respectively). In figure 4b, the central node's N CE is < 1, 1, 1, 2, 2, 2, 2 >. We apply entropy [45] to assess the mapping distribution in NCE. If a node has intricate neighbourhood information, namely a large entropy value, then it can be treated as the boundary node of a community. Here we use the Shannon Entropy to quantify the uncertainty of the NCE. For a node x, given the community mapping function C G , its boundary score BS(x) can be calculated as follow: If |Γ(x)| = 1, its boundary score is set as 0. It can be easily proven that the maximum value of the numerator is log(|Γ(x)|), thus the BS value is always among 0 and 1. Higher BS score of a node indicates its neighbourhood community attributes are more various. For example, the central node in figure 4a has a boundary score 0.5545 while in figure 4b the boundary score equals to 0.3509. It is more precise since in figure 4a, the central node is on the overlapping section of three communities while in figure 4b it stands between two communities.

Algorithm 1: Boundary Score Calculation
Input: Graph G = (V, E), Community Mapping Function C M and node x.
With the help of Boundary Score, the definition of consistency score (CS) is defined as: The maximum value of CS of a node will be achieved when there is only one type of community in its neighbourhood. Larger CS value of a node suggests its neighbours' community attributes perform less uncertainty. This consistency measure can be viewed as a node centrality index evaluating the uncertainty of its neighbourhood clustering information.

Harmony Similarity Measure
As discussed before, due to the imperfection of community detection algorithms, there is no reason that link prediction methods should take the clustering results as the ground truth. Experimental results in section 4 will prove that the usage of community attributes with insufficient consideration might damage the community enhancement.
Consider the RA index [46]. The intuition behind this method is the resource allocation process on networks. The similarity function is formulated as: It can be interpreted as a way to quantify the information transmission efficiency, which is under the assumption that intermediate nodes between x and y will equally spread information towards their own neighbours. So equation 5 can be regarded as a measure of amount of information flow coming out of node x and received by node y.
Consider the information spreading with community attributes. Instead of spreading to neighbours uniformly, the information flow might be measured inaccurately by the uncertainty of intermediate nodes' neighbourhood information. That is to say, in this case, the information flow is not point-to-point but in the community-to-community pattern.
In other words, creating links between nodes that have higher consistent common neighbours is equivalent to creating links that are more likely to have the same community attribute. Here we define the harmony(HM ) value to evaluate this consistency between node x, y, namely: where CS is the consistency measure. Through equation 6, it is clearly seen that the HM index is a second order similarity measure via entropy. The HM score of two nodes is higher if their common neighbours have larger average CS value. Following the definition of consistency, a node with higher consistency value indicates that it is more likely to be a central node of a community. Then nodes x, y will yield a large harmony value if they share a neighbourhood of central nodes, suggesting that x and y are more likely to share the same community.

Algorithm 2: Harmony Score Calculation
Function C M and nodes x, y. Output: Harmony Score HS(x, y).

Evolution Transformation
According to equation 6, nodes in the same community are expected to have higher HM score. It is a desirable characteristic, but it might also accelerate the enhancement of fractured community at the very beginning if solely based on the harmony index. Therefore this enhancement ability of link prediction is still insufficient. We need to control the evolutionary process by community size to determine whether it is time to adding reinforcing edges or not. Firstly we explain the two stages of HAP method in detail. As illustrated in figure 1, the enhancement procedure can be separated into two processes. The first process is to add links between fractured communities, which adds revising edges to mend broken communities. After that, the enhancement measure tends to strengthen those relatively large-scale communities by adding reinforcing edges to reinforce the outputs of community detection algorithms.
In order to automatically transform the enhancement procedure, the variables in such process need to be carefully designed. Following the demonstration of figure 1, the minimum community size escalates. It can be seen that in figure 3, comparing with the connective frequency between different community in the ground truth result, the connection among fractured components from Infomap are much more frequent. The merging of small communities should have higher priority at the beginning. For two nodes x, y with different community labels, HAP method tends to add link between them if the communities they belong to are relatively frequent to connect with each other.
Here we define Community Size Attribute (CSA): CM is the connection matrix. Equation 7 calculates the ratio between inter edges and the intra edges for smaller communities when C x = C y .

Algorithm 3: Community Size Attribute
Input: Graph G = (V, E), Community Mapping Function C M and node x, y. Output: CSA value CSA(x, y).
As aforementioned, when C x = C y we do not want to enhance the community when it is relatively small, since reinforcing small communities too early might cause improper community detection result. Empirically we set CSA = N Cx / max i {N Ci } when C x = C y , which performs satisfactorily in experiments. The CSA value will yield higher value when the size of community gets larger during the revising process.
Generally, the CSA index can be re-garded as the indicator of connection possibility between communities since it utilizes the community attribute of nodes. On the other hand, the HM index explicitly points out the detail about which pair of nodes should build connection. Combing those two indexes together could achieve the community enhancement measure with desired automatic transform of procedure.
Following this, combine equation6 and 7, the similarity function of HAP method is listed below: HAP (x, y) = CSA(x, y) · HM (x, y)

Algorithm 4: HAP Method
Input: Graph G = (V, E), Community Mapping Function C M and Number of Adding L. Output: With all the preparation work, the community enhancement process is demonstrated in algorithm 5. In the experimental section, we will replace the HAP method with other link prediction methods to verify its validity.

Datasets
Twelve networks are tested in experimental process, including a network consisting of 62 dolphins in a community living off Doubtful Sound, New Zealand (Dolphins, for short) [47], network of friendships among 34 members of Zachary's karate club (Karate, for short) [48], books about US politics sold by the online bookseller Amazon.com in 2004 (Polbooks, for short) [49], a mapping interactions between Science in Society actors on the Web of 12 European countries (Eurosis, for short), an online hyperlinks network between weblogs on US politics (Polblogs, for short) [50], a network of the relationship between publication and the corresponding word from a dictionary (Cora, for short) [51]. A series of citation network on different sub domains, listed as Cora Artificial Intelligence( Cora AI, for short), Cora Human Computer Interaction (Cora HCI, for short) and Cora Operating Systems (Cora OS, for short) [52], three subsets of the 20 newsgroups dataset which comprise around 18000 newsgroups posts on 20 topics (News 1, News 2, News 3, for short) [53]. 1 Details of the twelve datasets are listed in table 1. The column of Transitivity indicates the fraction of close triangles in the network system, which is an indicator of connectivity. N C stands for the ground truth number of clusters in the network. To demonstrate the community structure, the index of Intra is defined as the ratio of edges within communities. L is the hyperparameter of edge increment for each iteration, which is approximately proportional to the number of edges in the network system.

Baseline Methods
The kernel of HAP method is the similarity paradigm link prediction algorithm. In order to verify the performance of proposed HAP method, it is compared with six other link prediction methods, including JA [54], PA [55], CN [20], CN1 [36], RA [46] and RA1 [36].
• PA(Preferential Attachment): s(x, y) = |Γ(x)| × |Γ(y)|. It is solely based on degrees under the assumption that higher degree nodes tend to connect each other and independent with network's topology information.
• CN1(Adjusted Common Neighbour): Different from CN, CN1 takes clustering information into consideration. It gets a bonus point if the common neighbours of nodes x and y belong to the same community with them.
• RA1(Adjusted Resource Allocation): Same as CN1, the numerator term in RA gets additional point for 1. All datasets are available on https://github.com/vlivashkin/communitygraphs common neighbours being in the same community with nodes x and y.
The community detection algorithms concerned here are Infomap, Louvain and Label-Propagation, all of which have been discussed previously. All seven link prediction methods are aggregated with those three community detection algorithms to get twenty-one combination, which are tested on twelve real-world datasets. Further details will be provided in the following subsection.

Evaluation Measures
In order to quantify the quality of community detection result, as well as measuring the improvement of graph enhancement, the widely used Normalized Mutual Information (NMI) evaluation methods will be introduced here: where MI [56] stands for Mutual Information score and H is the Shannon Entropy function. If we take X as the algorithm output and Y is the ground truth community structure, value 1 means perfect correlation while 0 stands for no mutual information. That is to say, higher NMI values mean better community detection results.
In addition, the correction ability of link prediction methods is another desirable characteristic. To quantify this ability, the fraction of revising edges will be discussed here. Furthermore, to express the automatic transition between two stages, the dynamic about fraction of revising and reinforcing edges will be demonstrated. Last but not least, to test the generalization ability and numerical stability, the difference between the original NMI value and the final output NMI value will be compared.
Meanwhile, we illustrate the average fraction of revising edges of all link prediction algorithms among three different community detection methods. Since the damping factor N Cx in equation 7 is clearly not suitable for all situations, only part of real-world datasets about the dynamic between two stages will be demonstrated.

Evaluation of NMI
In this section, we demonstrate the numerical experimental results on twelve networks. Since the ground truth community structure behind those networks are all available, we compare the algorithm output with the ground truth by applying the NMI measure. The result of best NMI performance of all link prediction methods among three different community detection algorithms are demonstrated in figure 5.
For each network, we independently apply the different twenty-one combinations of link prediction methods with community detection algorithms and repeat the link 10,  figure 2 already demonstrated that the Lovain method achieved satisfying result and the community enhancement task wouldn't be significant. adding and clustering for ten iterations as the community enhancement measure. The results in figure 5 are the best performance for each link prediction methods among three different community detection algorithms. The corresponding ranking is listed in table 2. As we can see in table 2, our proposed HAP link prediction method has leading performance in 10 out of 12 networks, especially in the dolphins network where it reaches the maximum value of NMI. Not limited to the best performance of NMI values, the improvement on each real-world datasets are still significant. Since there remains uncertainty in the community detection section, several link prediction methods might get leading performance since they acquire better community detection result at the beginning of community enhance-ment process (demonstrated in algorithm 5). Here we provide such information in figure 6, where red part indicates the final result is decreased while green part shows the improvement between the initial partition result and the terminal output after the final round of graph enhancement.

Evaluation of Revising Edges
Taking a step further to explore the reason of such leading performance by HAP method, we need to consider the role of revising edges in the community enhancement task. According to inductive biases, it is believed that the connection of revising edges will deeply affect the community detection methods and lead those algorithms to better NMI performance. As shown in table 4, each value indicates the average fraction of revising edges among three community detection methods for the corresponding link prediction method. For example, if the accumulating fraction of CN index in complex network system on three community detection methods are 6, 9 and 12, the corresponding value in this table is (6 + 9 + 12)/3 = 9. The best value on each network is highlighted. As can be seen from table 4, the proposed algorithm can achieve the best performance in all datasets with overwhelmingly highest fraction of revising edges. Additionally, comparing the CN and RA index with their community attributes version CN1 and RA1, the experimental results on revising fraction elucidate that improper consideration of community attributes will bring damage upon the correction ability of enhancement measure.
Not only the revising edges, the reinforcing edges also play an important role in mending fractured communities.  Subfigure 8a to subfigure 8b represents the first stage of graph enhancement, which makes connection between fractured components and turns them into a complete community. While from subfigure 8b to subfigure 8c shows the reinforcing process to enhance the correct community detection result.
Thus we design our HAP method with evolution process to transform from adding revising edges to reinforcing edges. The transformation has been successfully captured in several datasets. Demonstrated in figure 7, it can be seen that the link prediction method has the ability to automatically transform from revising to reinforcing process. The illustration of transformation about HAP method on Dolphin network is presented in figure 8, where the evolutionary process between two stages is clearly captured. Last but not least, table 5 shows the sign of difference between the original NMI value and the final output NMI value. In this table, the improvement is labelled with the sign + in red. It can be seen that our HAP method has the greatest application stability and suits for 17 out of 20 cases.

CONCLUSION AND FUTURE WORK
In this paper we propose the HAP method to fill the void of link prediction based network community enhancement method. Combing the HM index and the CS index, it can be treated as a iterative method which first determines the connection in global perspective (community level) and then focuses into the neighbourhood local information (node level) at each iteration. It has desirable portability and simplicity with low computation cost. Compared with other baseline methods on real-world datasets, we find that our proposed novel index has better performance in most cases. Furthermore, the HAP method does not require any prior knowledge about the distribution or number of communities. Finally, thanks to the iteration paradigm, all local link prediction approaches are no longer bounded by the two hop distance.
There still remain some works that need to be further studied. In this paper we only consider adding edges to the network system, but the removal of existing edges also needs to be concerned. And the square root term in the similarity function of proposed method is an empirical modification term which cannot suit all situations. In future work, we will further explore the preprocessing ability of HAP method in the circumstances where nodes have additional attributes like the node classification tasks or the graph classification tasks.