An optimisation tool for robust community detection algorithms using content and topology information

Community detection is an active area of network science research and over the years, a wide variety of community detection algorithms have been proposed to find the communities in the network. Community detection is also named as graph partitioning, in much of the literature [13, 14]. It is tempting to suggest that community detection and graph partitioning are really addressing the same question, since both their aim is to identify groups of nodes on a network that are better connected to each other than to the rest of the network. However, it is very important to stress that the task of graph partitioning and community detection can be distinguished from one another based on whether the experimenter fixes the number and size of the groups or it is unspecified [15]. Graph partitioning is the problem of partitioning a graph into a predefined number and size of clusters. It has been pursued particularly in computer science and related fields with applications in parallel computing and very-large-scale integration (VLSI) design, whereas, in the community detection, which has been pursued by sociologists and more recently by physicists and applied mathematicians, with applications especially to social and biological networks, the number and size of clusters are unspecified. Furthermore, the goal in the former is usually to identify the best division of a network regardless of whether or not a good division existed. In case there are no good divisions existing, the least bad one will be identified as the solution. On the other hand, in the latter, the algorithm only divides the network when good divisions exist and leave the network undivided in case there are no good divisions existing [3, 15].

The community detection algorithms can be classified in different ways, and depending on the selected criteria, one algorithm can belong to more than one category. Among them, those based on modularity maximisation form the most prominent family of community detection algorithms such as fastgreedy algorithm [16] and Louvain algorithm [17].

Fastgreedy algorithm is an agglomerative hierarchical clustering method proposed by Newman [16]. The algorithm greedily maximises the modularity function Q and starts the process by assigning a different community to each node in the network. Then, at each stage in the process, the pair of clusters that yields greatest increase of modularity or smallest decrease is merged until only one cluster remains containing all nodes in the network. The whole procedure can be represented by a dendrogram (hierarchical tree) that illustrates the order of the mergers. Cuts through the dendrogram at different levels give different partitions into communities. The optimal community cluster can be found by cutting the dendrogram at the level of maximum Q.

Louvain algorithm is a hierarchical agglomerative optimisation method proposed by Blondel et al. [17] and attempts to optimise the modularity of a partition of the network. The optimisation is performed in two steps that are repeated iteratively. This algorithm starts with each node in the network belonging to its own community. Then, in the first step and for each node in the network, the algorithm uses the local moving heuristic to obtain an improved community structure by moving each node from its own community to its neighbours’ community and evaluating the gain of modularity associated with the moving of the node. The node is then placed in the community for which the modularity change is the most positive. If none of these modularity changes is positive, the node stays in its original community. This process is applied repeatedly and sequentially for each node until all the nodes in the network are considered, and no further improvement can be achieved. This concludes the first step. The second step of the algorithm consists of building a new network from the communities discovered in the first step. Therefore, the individual nodes in the new network are the individual communities from the first step. In this new network, there will be an edge between two nodes if there were edges between the corresponding two communities in the previous step. The weights of those new edges are the sum of the weights of the edges between nodes in the corresponding two communities. The edges between nodes of the same community in the first step will lead to self-loops for this community node in the new network. Once the second step is completed, it is possible to replay the first step and iterate again if necessary. The two steps repeat iteratively and stop when there is no more change in the modularity gain, and consequently, a maximum modularity is obtained.

Another popular method widely used to find communities in the network is based on the random walk. An example includes Walktrap (WT) algorithm which is proposed by Pons and Latapy [18]. Walktrap algorithm is based on the principle that random walks on a network tend to get ‘trapped’ into densely connected parts defining the communities. In this method, the authors propose using a node similarity measure based on short walks to capture structural similarities between nodes instead of modularity to identify community via hierarchical agglomeration. The algorithm starts by assigning each node to its own community, and the distance for every pair of communities is computed. Communities are merged according to the minimum of their distances and the process iterated. After n − 1 steps, the algorithm finishes and gives a hierarchical structure of communities called a dendrogram. The best partition is then considered to be the one that maximises modularity.

Information theoretic algorithms are another major type of community detection clustering algorithms that use the concept of information theory to find community clusters in the network. Infomap algorithm is an example of information theoretic algorithms proposed by Rosvall and Bergstrom in [19].

Infomap algorithm characterises the problem of finding the optimal community clustering in the network as the problem of finding the most compressed (shortest) description length of the random walks on the network. It uses a random walk as a proxy for information flow in a network and minimises a map equation, which measures the description length of a random walker, over all the network clusters to reveal its community structure. To represent the community structure, the algorithm uses a two-level nomenclature based on Huffman coding: a level to distinguish communities in the network and the other to distinguish nodes in the community. In practice, the random walker is likely to stay longer inside communities, and therefore, in the process of finding a community containing few inter-community links, only the second level is needed to describe its path, leading to a compact representation.

However, most of these algorithms are classified as global algorithms, which require access to the information of the entire network and make use topology information and largely ignore the attribute information [2].

Another property of similar interest is transitivity or global coefficient clustering, which is defined as the tendency between two nodes to be connected if they share a mutual neighbour [20]. In terms of network topology, transitivity is defined as the presence of a heightened number of sets of three vertices with edges between each pair of nodes (triangles) in the network.

Empirical studies have found that the concept of transitivity applies in about 70–80% of all cases across a variety of small group situations [21, 22]. Huijuan and Shixuan [23] proposed a graph clustering algorithm called SNGC that considers both connectivity between nodes and shared neighbours. Their experimental results show that the proposed algorithm provides promising results and could be applied to the analysis of social networks, computer networks, bioinformatics, etc.

Another common occurrence in networks is that similar nodes associate with each other more often than others (e.g. in social networks, people choose to be friends with people who share their beliefs). This property is known as homophily [24]. Traud and Kelsic [25] show that a set of nodes’ attributes can act as the primary organising principle of the communities. Several studies have been performed to investigate this phenomenon of homophily, which is summarised in McPherson et al. [24].

There have been modifications and revisions to many methods and algorithms already proposed. A comprehensive survey of community detection in graphs has been done by Fortunato in [2]. Other reviews available in the literature are by Bedi and Sharma in [26] and Plantié and Crampes in [27].

Recently, there have been several studies [28‐33], [34] showing that the combination of attribute and link information to detect communities in a network can improve the clustering quality. Most of these studies propose new algorithms that aim to use both sources of information; however, most methods use all attributes the same way without considering which ones may influence the community structure more, and lack the flexibility of balancing the information coming from network adjacency matrix (link information) and its node attributes.

Considering more than one source of information for community detection could produce meaningful clusters and improve the robustness of the network. Therefore, a pre-processing approach that considers both the attribute information and connectivity information aspects of the network for community detection is presented in this work. It should be noted that this work does not attempt to introduce a new community detection algorithm and rather proposes a pre-processing step to improve the performance of the existing community detection algorithms and enable them to execute in unreliable data network environments with better results.

In this paper, a network is represented as an undirected network G = (V, E, A), where V is the set of nodes and E is set of edges between nodes. Each node Vi ∈ V is associated with an attribute vector (\({\text{Att}}_{i}^{1} , \ldots {\text{Att}}_{i}^{d}\)), where d is the attribute dimension and i represents the node ID.

The main goal of this work is to find K non-overlapping communities in the network where the community (C) is defined as a list of non-empty node subsets: C = {\(C_{1}\), \(C_{2} , \ldots ,C_{k}\)}, and \(V = \cup_{i = 1}^{k}\)\(C_{i}\) that satisfy \(C_{i} \cap C_{j} =\) ∅ for any i ≠ j.

The attribute similarity between nodes V_i and V_j within the same cluster is determined by examining each of d set of attributes on the two nodes and reflect on the strength of the relationship between them in terms of their attribute values.

It must be emphasised that irrespective of the similarity metric considered to find the weight of attributes, first, the similarity between the attribute values of each pair of nodes belonging to the same local cluster needs to be calculated. The procedure is as follows:

Let \(X_{N.d}^{i}\) be the similarity matrix for cluster i with N nodes each with d attributes, the local attribute weight for cluster i is obtained by adding the appropriate dimension attribute of each node in the cluster to form a vector of 1 × d size and expressed as:

The weighting for the entire network is then calculated by adding the corresponding attribute of each local attribute weight (sum of the vectors) to form another vector in 1 × d size. It is formally defined as:where \({\text{LW}}_{d}^{i}\): the local attribute weight for cluster i and W: attribute weights of the node in the network.

It is worth mentioning that the weights assigned to the attributes in the parameter learning phase \({\text{LW}} = \{ Lw_{1} ,Lw_{2} \ldots Lw_{m} \}\) range between 0 and 1.

Whether or not a certain subset is optimal depends on the similarity metric employed. The question about what are the best similarity measures between nodes to choose, for different types of attribute data, is beyond the scope of this work. In this work, a Jaccard similarity coefficient is used to define the attribute similarity between nodes in the same cluster and to find the weight of attributes (W) during the parameter learning phase. For an overview of the research work on determining the most meaningful similarity measures in various fields and for different types of data, see [42, 43].

where \(J(A_{i} ,A_{j} )\) returns a value between 0 and 1, with 0 denoting no similarity and 1 denoting identical sets.

Furthermore, since in this work Jaccard similarity is used to measure attribute similarity between nodes, the \(X_{N.d}^{i}\) could be defined as the Jaccard similarity matrix for cluster i. The weighted attribute similarity \(Wa_{\text{sim}} \left( {i,j} \right),\) between any two nodes i and j is defined as follows:where each node has d attributes and \({\text{Att}}\_i\) is the attribute vector of node i.

The pseudo-code outlining the entire procedure with Jaccard similarity is listed in Algorithm 1.

As highlighted in Sect. 3, different attributes have different significance for assessing the similarity between the nodes in the same community clusters; therefore, the attribute weighting method is proposed. In this section, the performance of the proposed attribute weighting method is experimentally evaluated.

The evaluation is done by checking how well the weight of the attributes (W) obtained by the weighting method match with the actual important attributes and is presented in Fig. 2.

Figure 5 shows the attribute weights obtained by the weighting method for the four datasets under consideration. It is obvious that the attributes have different weight strengths and order of importance for different datasets. However, looking at the attribute weights of the four data sets, it is clear that four specific attributes (student, gender, dormitory and year attribute) have the highest weighting values across all four data sets. Anyway, the remaining attributes (high school and major/minor attribute) do not have strong influence on the community structure, hence weighted with a very small value in the attribute weighting stage.

Moreover, the comparison between Figs. 2 and 5 shows that the parameter learning phase achieves almost the same results in most cases, whereas the attribute importance order is either same or only slightly different due to small differences in the attribute correlation. For example in Caltech36 dataset, the order of importance attributes are student, gender, year and house with attribute weight values 0.4695, 0.3102, 0.2195 and 0.2193, respectively. In comparison with Fig. 2 and for the case of the Fast Modularity algorithm as an example, the order is changed to student, gender, house and year attribute, achieving Jaccard index values of 0.2772, 0.2412, 0.1746 and 0.1239, respectively.

Furthermore, to evaluate the performance of the proposed weighting method in handling noisy data, Fig. 6 shows the values of attribute weight for the four largest weighted attributes obtained by the weighting method when the percentage of removed edges varied from 0 to 50%. From the figure, it is worth noting that the ordering of weights is remarkably stable and the attribute weighting method shows an effective performance by getting rid of the noisy datasets and correctly weights attributes according to their importance.

To further assess the parameters analysis phase, the number of initial clusters identified at local clustering stage along with the value of α against the per cent of removed edges, for the four datasets, is reported in Table 1.

The results in Table 1 indicate that the noise has no significant influence on the value of α. In other words, the method used to define α value (see Eq. 12) is somewhat stable. In addition, it is clear that local crusting tends to partition data to a larger number of initial clusters. Considering Reed98 dataset, for example, when the missing edges varied from 0 to 50%, the values of α and the number of obtained initial clusters were {0.808, 382} and {0.823, 446}, respectively.

It is also worth noting from Table 1 that the value of α is not related to the number of initial clusters found by the local clustering stage. In some cases, higher value of α is obtained when more initial clusters are found. For others, however, the value of α increases when fewer initial clusters are found. Considering Reed98 dataset, for instance, when the missing edges increased from 15 to 20%, both α value and the number of initial clusters increased from {0.814, 399} to {0.816, 405}, respectively. On the other hand and for the same dataset, when the missing edges increased from 5 to 10%, the value of α increased from 0.812 to 0.813; meanwhile, the number of initial clusters decreased by 3. However, the value of α for the four considered datasets is always higher than 0.75. This value is in agreement with what was observed in Sect. 4.1.1.1, where the connectivity information contains more useful information than the shared neighbours or attribute information (α ≥ 0.5) and to get high modularity the value of α should be higher than 0.7.

Overall, the results clearly demonstrate that the parameter learning method has the ability to extract essential and informative attributes and to weight them to reflect the relative importance of attribute in community clustering tasks.

In this subsection, using the optimal parameters determined using the parameter learning phase (as discussed in Sect. 4.1), the performance of the pre-processing approach is evaluated.