Abstract
In a real-world, networked system, the ability to detect communities or clusters has piqued the concern of researchers in a wide range of fields. Many existing methods are simply meant to detect the membership of communities, not the structures of those groups, which is a limitation. We contend that community structures at the local level can also provide valuable insight into their detection. In this study, we developed a simple yet prosperous way of uncovering communities and their cores at the same time while keeping things simple. Essentially, the concept is founded on the theory that the structure of a community may be thought of as a high-density node surrounded by neighbors of minor densities and that community centers are located at a significant distance from one another. We propose a concept termed “community centrality” based on finding motifs to measure the probability of a node becoming the community center in a setting like this and then disseminate multiple, substantial center probabilities all over the network through a node closeness score mechanism. The experimental results show that the proposed method is more efficient than many other already used methods.
Introduction
Network analysis has countless uses in engineering systems, computer science, biotechnology, the humanities, and different natural and social sciences. For instance, the pattern of rumor diffusion on social networks is analogous to the pattern of disease distribution. Furthermore, the structure of the human brain network, with its connections through multiple chunks, has a remarkable structural likeness to the social media giant Facebook network. With the speedy growth of social networks and the Internet, the prominence of networks is progressively felt in daily life. Networks are being discussed in broader contexts and possibilities in the Big Data era. A group of nodes forms a network, and edges connect these nodes. It can generally be partitioned into directed/undirected and weighted/unweighted graphs. Curiously, several real-world networks have dynamic properties and comparable structures.
People can learn a lot about how complex systems work and how they change over time by studying the structure and characteristics of complex networks [1]. The community relates to the node-set with directly adjacent internal links but sparse external links in the network. The connection relations formed by the community are the community structure [2]. Members of a community are more similar within the same community, but there are noticeable differences between members of different communities [3]. As a result, the network’s community structure makes evident that there is a lot of diversity and connection between network members. Extracting the network’s community structure is very important for network science [4]. Community detection can help people identify communities in networks, draw inferences about the network’s structural organization, and understand the relationships between nodes in the network. As a result, it can develop several intelligent services, such as setting precise marketing strategies, finding drug targets, and extracting social network information for analysis and prediction [5]. The effectiveness of these applications has also led to more scholars getting involved in community detection studies, which is what these applications are suitable for.
Generally, algorithms for community detection can be alienated into two main parts: Global approaches for mining communities necessitate information about the whole network structure, which entails more time complexity and is not appropriate for distinguishing communities in complex networks, classified under the term “largescale.” Among them are the Girvan–Newman algorithm [6] (which, to the authors’ knowledge, is the first method that aims to optimize Q), the approach relating to information centrality [7], and some others (please see [5] for a review). Unfortunately, the worst-case time complexity of global methods is exceptionally high. As a result, these approaches cannot be implemented effectively in vast networks with millions of vertices and billions of edges. In contrast, local approaches can mine communities for local structural information, deprived of the necessity for a global understanding of the complete network. These techniques resolve the restrictions of global approaches. Nonetheless, the precision of more or less local approaches may not be promising because there isn’t enough information about the world around us [3, 8]. The time complexity of local methods is usually near-linear, and they have a tolerable time complexity in the analysis of large-scale networks [9]. Numerous local methods have been suggested to address the previously mentioned constraints of discovering communities. They are solely based on node-specific information. A recent study surveyed local methodologies based on different optimizing techniques [10]. When tested experimentally, local approaches are split into link clustering [11–13], label propagation algorithms [14, 15], local expansion optimization methods [16, 17], and clique-percolation based methods [18, 19]. Local expansion optimization algorithms are commonly utilized in large networks for local community detection because of their improvements in efficiency and accuracy. These methods aim to optimize local community qualitative functions from initial nodes [20, 21] while being dependent on the initial seeds and pre-existing factors. X. Ding et al. suggested a local optimization algorithm. It identifies different types of communities and then runs local expansion methods and boundary re-checking sub-processes [22]. Lee et al. presented a greedy clique expansion (GCE) procedure [23]. It picks individual cliques for initial seeds and, via greedy optimization, expands those seeds. Huang et al. [24] Presented an algorithm using a quality function based upon similarity and a local tightness expansion algorithm (LTE) to uncover community structures out of a random vertex. Furthermore, density-based clustering algorithms deserve to be mentioned as well. E. Baracchini et al. came up with a density-based clustering method based on the DBSCAN algorithm and could be used to find community structures [25] Nonetheless, as with most other density-based clustering algorithms [26, 27], it is still dependent on subjective parameter selection and does not provide an automated method of determining the suitable parameters
Our approach in this study is to take advantage of the node density notion in a network and utilize the resulting distance setting to design an efficient algorithm that concurrently discovers the centers that form communities. We are trying to develop an index of community centrality to measure the relative importance of a node to its neighbors within the community by finding the three-node motif involving node i. Centers in some communities are more likely to be found in nodes with a greater community centrality index than in others. We will then be able to group the rest of the nodes into communities using a node closeness procedure to calculate the closeness score, which is based on Katz’s centrality.
By including topological, and structural modeling in the community detection process, we demonstrate that our technique is more accurate in detecting communities in a variety of By including topological and structural modeling in the community detection process, we show that our method is more accurate in detecting communities in a variety of benchmark systems, both real-world and synthetic. Our approach’s advantages are especially relevant for networks with widely distant nodes. Nevertheless, our technique may have difficulty identifying distinct communities in some networks where the centers have more links because of the less defined boundaries within communities. Motivations for this study: The cluster centers are most likely to be at a local optimum. This issue has an impact on the clustered outcomes and must be addressed. Some algorithms visually identify cluster centers on the decision graph, which may impact clustering performance. As a result, it is vital to figure out how humans affect things and get automatic cluster center identification.
Our main contributions to this algorithm are: High density and long distance should be characteristics of cluster centers. Therefore, we proposed the node density term based on triangular motifs. With a high strong-tie index, a center node should have more neighbors, and the neighboring nodes have a greater degree of connectivity between themselves. Aiming to solve the problem of cluster centers quickly falling into a local optimum, our algorithm achieves the goal of automatically selecting cluster centers while avoiding the subjectivity of the manual selection process by selecting the node with the highest density score to be the center of the community. Based on the observation that shows two nodes with high closeness centrality may be in the same community. We introduced the node’s closeness function to form communities. We test the performance of our algorithm using multiple typical benchmark data sets, and we evaluate the clustering results using two well-known evaluation cluster quality indicators, NMI and Modularity. Experiments comparing the proposed clustering algorithm to seven other algorithms demonstrate its effectiveness and correctness.
The rest of this study is structured as follows. We provided the related work about density and clustering approaches based on node closeness for the detection of communities in Section 2. Section 3 explains the proposed algorithm in detail. Section 4 describes the experimental results. Section 5 offers the conclusions.
Related work
In recent years, clustering techniques based on density have become extremely prevalent in cluster analysis [28]. DBSCAN (density-based spatial clustering of applications with noise) is considered to be the first effort in this field [29]. In DBSCAN, the density is locally stated as the neighbors of a data point inside a given range. Provided a suitable density threshold and a minimal cluster size μ, high-density areas can be assigned to various clusters, and points can be thrown down as noise in areas with densities smaller than this threshold. Social network analysis has benefited from the use of the density-based clustering method. Two algorithms, DENGRAPH [30] and [31], DBSCAN, were extended to discover communities, introducing two distinct distance functions into the grouping procedure. The interaction-based distance was introduced by DENGRAPH, which calculates the total number of interactions between two users in a social network [30]. [31] introduced a novel technique for cluster center selection that uses MNN (M nearest neighbors), density, and distance to obtain initial cluster centers. The authors demonstrate that the strategy yields high-quality initial cluster centers.
TThere have been some alternative algorithms proposed throughout the last decade. To detect local communities, Ding et al. introduced RTLCD, which is a two-stage approach that includes detection of a local community using core detection, as well as community extending from these cores. It has a time complexity that is close to linear, but it has low precision [32]. Local similarity-based techniques are usually less time-consuming to compute but less accurate than global similarity-based approaches. There are many ways to use local similarities. These include label propagation-based methods, local modularity-based methods, and many hierarchical clustering techniques, among others. In [33], the local method, ECES, was devised by Berahmand et al., based on the detection and expansion of the core nodes. A centrality criterion is applied that delivers top scores to well-embedded central nodes. The weights between borders are first determined via a similarity index, and then the core supremacy of the center node is computed to choose core nodes. The next stage is to extend the core nodes with a member feature. The resulting communities are then produced in the blending process.
Wang et al. offered the LCCD method for community detection [34]. This technique initially locates the center nodes of communities due to its structural centrality, which is calculated by taking into consideration distances between nodes and local density. Following the identification of core nodes, it grows the local community from either the interior central nodes or the exterior nodes of the network. A new method based on neighborhood nodes and the criterion of local similarity has been suggested by Eustace et al. [35]. The original communities are first detected in this process, and the local communities are probably integrated into global communities during an iterative step. First, the graph selects a random node. Then, the similarity between the node and its neighbors is determined. (α-closing). If the similitude value is larger than α, one local community is allocated to the chosen node and its neighbor. α is the average neighborhood node ratio for the full diagram, and the relationship is detailed in [35]. The similarity between the communities is then calculated (β-close) during the combined stage, and if the result exceeds ß, two communities are united. In all local communities, β is the average neighborhood ratio. (Similarity ratio) This strategy is based on the detection of significant centers that are as remote from one another as possible. This strategy is the foundation of several community detection techniques. Another approach for large-scale networks that has been presented is the G-CN method [36]. This methodology uses an initial community discovery label propagation method. In contrast to LPA, G-CN merely updates boundary nodes in each cycle depending on the number of shared neighbors and not the label frequency. However, this method, like LPA, has some problems, like unstable communities and a hard time finding a good number of communities. To address these issues, SDGCN decided to introduce a two-phase method to identify communities [37]. The first stage aims at enhancing G-CN results using a novel updating approach without raising the linear complexity. It needs minimal label modifications, which results in inconsistency and a reduction in execution time. A new measure is utilized in the second stage to integrate communities adequately. In [38], a game theory algorithm is provided, initially considering each node as a single community and then randomly selecting one node. This node determines whether to join or leave a community, whether to modify its community, or whether to keep its existing status Using information from its adjacent communities. Randomly picking nodes and making decisions keeps going until no node wants to change its space.
Proposed method
Our algorithm is based on the idea that a community’s center node must be densely enclosed by other community members, implying that it is dense. Our algorithm also recognizes that the neighbors of the central node might not be all that connected. Nodes that are close together should be in the same community. Our technique, as shown in Fig. 1, is composed of three steps: first, we compute the node density based on triangular motifs; second, we determine the center node of each community based on the first step (the node with the highest density score is set to be the center of the community). Once node density and node centrality are determined, the community detection algorithm is activated. During this phase, all nodes are regarded as though they belong to no community. Then, beginning with the highest center node, the community is assigned to it and its nearest neighbor. Following that, the next highest center node and its closest neighbor are taken to obtain the community. When all nodes have been assigned to any member of the community, the procedure is complete. In the following subsections, we will go over our method in further detail.
Density and node closeness based algorithm.
A complex network can be expressed as G(V,E), where V offers the set of nodes, and E shows the set of edges. A n x n represents the adjacency matrix of the graph or network for n number of edges and n number of vertices. A ij ∈[1] clarifies whether there is an existent link between V i and V j . Edge has existed as e (V i ,V j ). d i represents the degree of node v i . φ i represents the central nodes; it is used to measure the shortest distance from node i to all other higher ρ-score nodes. The node closeness between nodes i and j is represented by the symbol D ij .
Calculating node density based on motifs
For each node, we first compute a node density, indicated by ρ i . The strong-tie index (ρ s ) is a measure of density. As we all know, the degree of a node is defined as the node’s total number of neighbors. The higher the degree, the more neighbors the node has and, as a result, a higher local density. In our algorithm, the strong-tie index [39] is defined as the number of triangular motifs involving node i. With a high strong-tie index, node i have more neighbors, and the neighboring nodes have a greater degree of connectivity between them. The presence of such nodes is a significant indicator of the presence of communities. Before calculating node density, the FANMOD [40] tool will be used to find triangular motifs in the network. Motifs are small, connected subnetworks that a network displays at significantly higher frequencies than a random network would. FANMOD is a tool for fast network motif detection that relies on recently developed algorithms to improve network motif detection accuracy.
Identifying central nodes
When doing this phase, the primary goal is to delete non-central nodes based on their ρ-scores. According to intuition, a long distance should separate the center node from other central nodes with a higher ρ-score. The central node, on the other hand, will be physically separated from its neighbors (or lower ρ s nodes) by a short distance. As a result of this discovery, we define Core-Node-distance (CND) as φ i to aid in the selection of central nodes. To be more specific, the CND for ith node φ i is used to measure the shortest distance from node i to all other higher ρ-score nodes.
For example, consider the following: The value of the CND is as follows: If a node i has a low CND, that indicates i’s neighboring nodes have higher ρ s than the node i, then the node i will very doubtful be a central node. On the flip side, if the node i has a large CND, then it is necessary to go a long distance in the network to find a node whose CND is greater than the node i indicating that the node i is most likely a central node. In reality, regardless of their location, large φ i often occur at the global or local peak of the density indexes. As a result, we may then find the center nodes to be those that have mostly big φ i values.
We will use the FANMOD [40] approach to obtain a three-node motif to decrease the cost of computation associated with looking for node i’s neighbors. When a particular node i has first-order neighbors, we analyze them to see whether any of them has a bigger value of ρ
s
than the node i. If any of them do, we set the value of φ
i
= 1. Aside from that, we look at the second-order neighborhoods to see if any of them have higher ρ
s
. If so, we initialize φ
i
= 2. If not, we keep evaluating the entire node i’s third-order neighbors until we reach the end. Because of the community’s dense connectivity structures, a second-depth search within the area is usually sufficient. As a result, if we are unable to locate a node with a greater ρ
s
, we will often stop at φ
i
= 3 and not search any further. For various networks, such as email [41] and jazz [42], etc., the centers of the community are directly interconnected based on ground truth. In these circumstances, φ would be 1, would be one and could not be utilized to determine the centers for most nodes. We may define “community centrality” to account for the combined effect of local density and relative distance;
As shown in Fig. 2, nodes are colored according to their density order, and the length of edges represents the distance between nodes. The two blue nodes are structural centers in two communities. Based on the graph above, we can see that both of the center nodes are involved in four triangular motifs, implying that their ρ-score = 4, the highest density value in the graph. It will be determined how far away each node is from a center node using formula (3). Then, each node will be assigned to a community that shares the center node’s community.
A demonstration of the community’s center with an abstract graph.
The node closeness is calculated to assess how close the two nodes are to one another in terms of distance. The closeness of nodes can be thought of as the inverse of the distance between nodes. Calculating node closeness is possible using the node distance matrix. Consider the distance matrix A; the shortest distance or shortest path between nodes i and j is equal to A
ij
, where A is the distance matrix. Connections between nodes, on the other hand, do not always take the fastest route. When sending a significant volume of data from node i to node j, for example, we would employ all of the paths that are available to ensure that the data flow is as efficient as possible. Node closeness is the value that would be used to determine the maximum amount of data that can be transferred between nodes. Furthermore, the closeness of nodes can be thought of as a measure of how quickly information will move from node i to node j in a network. The Katz centrality approach serves as the foundation for our node closeness calculation. The formula below can be used to figure out the node closeness matrix.
The node closeness between nodes i and j is represented by the symbol D ij . d ijl is the weighted sum of pathways between nodes i and j that have a length of l and connect them. The coefficient value is denoted by F l . The number of hops or lengths is represented by l. The greater the node closeness score between node i and node j, the closer the two nodes are to one another. Similar to Katz’s centrality, this metric may very clearly detect the closeness of nodes, but in scale-free networks, it causes difficulty. The problem is the nodes, which are not in the community but connect at least two hubs. The closeness of these nodes might be very high and lead to the fusion of the two scale-free communities. The answer is analogous to the case of centrality, which adds the length of three closed sub-graphic centralities. Let j and node k connect to node j. The length of the three closed walks is formed when node node j and node k are joined. Then the closeness score is increased from node i to node j i to node j.
There are three steps in our method. The first step in determining node density has a time complexity of O(n), where n is the number of nodes. Computing the CND in the second step takes O(m) time, and sorting the values of δ requires O(n) time in case we used the sorting algorithm bucket. The third phase in the community detection process will take O(n) time. Therefore, our method’s overall time complexity is O(m + n). As an outcome, this approach has a linear time complexity and can easily be functional in a network that has thousands of nodes. For general networks, irrespective of density, Infomap’s time complexity scales as O(n2logn), but the efficient modularity-based approach Louvain has a lower time complexity that scales as O(n2). The Eigenvector technique has a time complexity of O(n log2n), whereas Fastgreedy has a time complexity of O(m(n + m)). LP takes a near-linear time, even though it is a deterministic approach that requires numerous repetitions to get unchanging performance LCCD’s time complexity scales as O(n2) while TS takes O(n3). The most precise method is usually the most computationally costly. As demonstrated in the following experiments, the suggested algorithm has higher accuracy and lower time complexity in comparison to existing methods.
Experimental results
The proposed method is implemented using the Python language with a 3.4 GHz Intel Core i7 processor, 16 GB of RAM, and a version of the Windows 10 system. On both real and simulated networks, our method has been tested. The results of our algorithm are compared to the ground-truth community structures and the results of other community detection methods to see how well it works. Generated networks are formed using the model of the LFR benchmark [43]. This also generates networks with power-law degree distribution and even with embedded communities within networks, whereas real-world networks seem to be of various sorts and sizes. The networks that we used in our tests are depicted in Tables 1 and 2, respectively. Furthermore, to assess the efficiency of community detection algorithms, we use two main evaluation criteria: modularity and normalized mutual information.
Synthetic Networks used in experiments
Synthetic Networks used in experiments
The real-world Networks used in experiments
In the experiments, we used two different criteria to measure the efficacy of a community detection algorithm. There is no ground truth community structure in real-world networks of different sizes and layers of community cohesiveness. As a result, we use modularity to assess the quality of community division and the cohesion of newly discovered communities. On the flip side, we use normalized mutual information (NMI) to properly assess the effectiveness of the proposed method against synthetic networks of defined ground-truth communities in measuring the similarity between the cultivated division and that discovered by techniques. One of the most widely used criteria for assessing the effectiveness of community partitions is modularity [44]. It is predicated on the assumption that a random graph will not have a clustering. As a result, the comparison between the entire network grouping and the correlating null model reveals the possibility of communities [45]. Modularity can be expressed in the following way:
Where the total number of edges in a network is donated by M, in the adjacency matrix, A ij denotes the relationship between nodes i and j. In the null model, P ij signifies the likely number of edges between nodes i and j. A typical option is P ij = ki kj/2M, where node i and node j degrees are represented by ki and kj, respectively. Ci is the community to which the node i was assigned to. The value of δ(Ci, Cj) equals one if i and node j belong to the same community, or else zero.
NMI stands for normalized mutual information, and it’s a metric based on information theory that’s widely used to test the efficiency of graph clustering techniques [46]. It allows for the comparison of covers and partitions. NMI is a measurement that can be described as follows:
Where A and B indicate discovered and real community partitions, and CA and CB denote the number of communities in A and B, correspondingly. The confusion matrix is denoted by N, and the number of nodes shared by communities C i and C j is denoted by N ij , where N j is the sum of N s column j and N i is the sum of N s row i. It’s worth noting that NMI’s value ranges from 0 to 1. Higher values indicate that an algorithm produces more accurate results.
Referencing [43], we created four benchmark networks to illustrate the efficiency of the suggested strategy. The relevant parameters for each benchmark network are listed in Table 1, where the number of nodes in networks that aren’t entirely related is represented by n, and the largest graph components are taken into account. k m is the averaged node degree, t1 is the negative exponent for the degree distribution, k max is the maximum node degree, t2 is the negative exponent for the community size distribution, minimum and maximum mass of communities are represented as c min and s max , mixing parameter is denoted by mu. Three of the four artificial networks have clear, non-overlapping community structures, while the fourth network has five communities that overlap. Network communities can be hard to find. To see how well different techniques work, we use Normalized Mutual Information (NMI). We set the mixing parameter mu to 0.1 to reflect the average ratio of the external degree to a total degree for each node for the sake of simplicity; the larger the mixing parameter, the more challenging it is to discover the community structure in networks. The experimental results for various algorithms on GN benchmark networks show that when the mixing parameters are less than 0.15, all algorithms get NMI = 1, indicating that all algorithms can identify the true community structures. However, as the mixing parameter increases, the performance of these algorithms degrades to varying degrees. When mu is less than 0.4, only four algorithms, namely LP, Infomap, Louvain, and LCCD, can reveal the true community structures on the ground. As the mixing parameter is increased further, the boundary between communities becomes hazier, and algorithm accuracy shies away.
As shown in Table 3, our approach to recognizing authentic communities delivers 100% accuracy in all networks with entirely disassociated communities. Figure 3 (a), LFR-2 has three communities formed out of 1000 nodes.
Performance assessment in the networks with ground truth
Performance assessment in the networks with ground truth
Generated networks results (a) LFR-2 with 1000 nodes and three communities. The result of our algorithm approves with the ground truth. b) Shows the two communities of LFR-4 suggested by our method.
Multiple real-world networks assess our algorithm, as seen in Table 2. One such karate club is the Zachary Network, a well-known de facto network. After a squabble between Club President John (node 34) and Instructor Hi (node 1), 34 members of the sports club are separated into two parts. Figure 4 (a) demonstrates that such communities found by our method are in line with Zachary’s results [47]. The leaders of both clusters are Node 1 and Node 34, which also reflect the ground truth.
The clustering results by the proposed method for real-world networks. (a) Zachary karate club network: the two communities we discovered are identical to the real communities. (b) Dolphins network: the two communities we discovered are identical to the two real groups of male and female dolphins. (c) Pol-blogs network: the two communities we discovered. (d) Networks of jazz musicians: this network has a clear tree structure, and the degree density index can be used to locate the centers.
N and M denote the number of nodes and the number of edges in the network, correspondingly. k m represents the average degree of the network.
The second network is Lusseau’s bottlenose dolphin social network [49], which is an undirected social network comprising common interactions among 62 bottlenose dolphins in a population off Doubtful Sound. Dolphins are depicted as vertices in this network, and a link is established between two nodes if the respective dolphins are seen together more frequently than observed throughout the seven years from 1994 to 2001. Male and female dolphins are separated into two categories. The ground truth and our results are demonstrated to be identical. Purple and blue, respectively, distinguish the two communities (see Fig. 4 (b)).
The third network is Amazon.com’s political book network, which has 105 nodes representing books about US politics that are available for purchase [51]. As seen by Amazon’s “customers who have purchased this book often purchase these other books” feature, the edges represent frequent book co-purchasing by the same purchasers. For this experiment, the political views expressed in these books are those of “liberal,” “neutral,” and “conservative.” Our detected communities have an NMI of 0.59 compared to the ground truth. Figure 4 (c) depicts the communities that were discovered.
Jazz musicians’ networks, the fourth network, modeled the topology structure of jazz musicians’ collaboration networks, which also encompass 198 bands that performed between 1912 and 1940 [42]. If two bands share at least one musician, they gain an edge. By using our method density-based as a criterion for selecting the core nodes, it results in modularity of 0.34 for the network. The result of the partitioning is depicted in Figure 3 4 (d). See Table 4 for a list of networks where we tested our method in the absence of ground-truth community divisions. As seen in the results, the networks ranged in size from a few hundred to tens of thousands. The following section includes a comparison of the proposed approach with other approaches.
Performance comparison in the networks deprived of ground truth
To evaluate our method further, we used the Python language with a 3.4 GHz Intel Core i7 processor, 16 GB of RAM, and a version of the Windows 10 system as a testing environment. We compared the results of our partitioning with those of five popular algorithms: Fastgreedy [56], Label propagation (LP) [57], Eigenvector [54], Infomap [58], Louvain [59], and two more state-of-the-art, LCCD [34] and TS [60], which are relatively new methods compared to the other methods. NMI and modularity were used as evaluation measures in this study. Table 3 shows that our method outperforms or is comparable to earlier algorithms that use the NMI criterion on networks with ground-truth communities, except for the American Football Network. The performance of our algorithm on the Polblogs dataset is slightly lower than that of TS. TS spent about three hours on the Polblogs dataset during the experiments, whereas our algorithm only took 12 seconds. The amount of time it takes for TS to work out is far more than its advantage over our method.
The number of communities is C, the modularity outcome is Q, and the normalized mutual information is NMI.
Here C is the number of partitions, Q is the modularity outcome.
Networks that do not have ground-truth data (like those in Table 4) can have the quality of their community detection findings evaluated using modularity. In-ground truth datasets, the NMI is the most effective evaluation tool. Because, as shown in 4, even though identified communities are often accurate, modularity is often not optimal. The actual modularity for the Karate and Dolphin datasets is 0.37 and 0.38, respectively, in the case of correct community detection (C=2). Nevertheless, for some techniques with incorrect detection, the obtained modularity is higher than the true value. Nonetheless, for datasets deprived of ground truth, the modularity measure is the only reasonable measure. The greater the modularity value, the higher the quality of the detected communities. Our partitions have lower modularity values than Louvain’s and Fastgreedy’s. The reason for this is that, unlike Louvain and Fastgreedy algorithms, ours isn’t expressly designed to maximize modularity. In large sparse networks with low rich-club integration, however (e.g., Power Grid, PGP, and CA-HepTh), our method’s modularity values are consistently superior to Eigenvector, Label Propagation, and Infomap, as shown in Table 4.
Real world application
In this section, we apply our algorithm to interesting real-world networks, the flavor compound network, to show its effectiveness in real-world applications.
Flavor compound network
The culinary practice has played a significant role in the history of mankind. In order to create a personalized diet, people nowadays pay close attention to the flavor compound profiles of culinary ingredients. This can be accomplished by utilizing the flavor compound network, which represents the compound similarity between various ingredients [61].
Local communities detected in the flavor compound network. The query ingredients are tuna, black pepper, and lime, which are colored in red, dark green, and yellow respectively.
Ingredients are represented by nodes in the flavor compound network. If two ingredients have similar flavor compounds, they have an edge. Based on the detected communities in the flavor network for the key ingredients, one can create new meals from current ones. For example, in our given scenario, we use the three basic flavors of a common recipe, Tuna with Lime and Black Pepper Sauce, as central nodes in the flavor compound network. We use our approach to analyze possible ingredient substitutions that typically contain flavor compounds by detecting their corresponding communities.
Figure 5 depicts the discovered communities. Tuna, black pepper, and lime are oversized, as are the center nodes of the communities. Our algorithm determines the three communities to which the three centers’ ingredients relate. We discover that the ingredients in each community share common substances with the center ingredient. The community members of the center ingredient tuna are various types of fish. Members of the black pepper group include various peppers and cayenne. The majority of the community members for center lime are orange-related elements. We could make another dish, such as Salmon with Lemon and Bell Pepper Saute, based on the detected communities, that has similar flavor compounds to the tuna recipe.
In this paper, we provide a simple and efficient method for recognizing community patterns in complex networks. Each community’s center node will be identified first as part of our method, and then the rest of the nodes will be classified into distinct communities based on a node closeness score computed using Katz centrality. The robustness of our approach, when compared to prominent techniques in the literature, is demonstrated in both real-world and synthetic networks in which ground truth is obtainable. In the majority of networks, the modularity obtained is, however, able to compete. Our method identifies underlying community partitions by performing a local expansion from the discovered centers, followed by a node closeness score method, which discloses the structures. Using this expanding technique, the entropy of seed selection and the manual selection of built-in parameters are avoided. From three perspectives, the results of our extensive studies on both real-world and synthetic networks highlight the benefits of our work. First and foremost, the structural centers-based local expanding technique speeds up the algorithm’s convergence to the ideal division and makes it run more consistently. Secondly, our approach also has no adjustable parameters in any of the steps of the algorithms. Finally, our approach not only successfully recognizes genuine community patterns but also properly identifies the hierarchical structure of a community. For some datasets, our algorithm has lower modularity values than those specifically designed to optimize the modularity. In the future, we may be able to make some significant improvements to our algorithm. It has the potential to be utilized for uncovering overlapping communities with some refinement. Also we may use our method to aid in solving some problems presented in [62, 63].