Community structure plays a significant role in uncovering the structure of a network. While many community detection algorithms have been introduced, improving the quality of detected communities is still an open problem. In many areas of science, adding noise improves system performance and algorithm efficiency, motivating us to also explore the possibility of adding noise to improve community detection algorithms. We propose a noise-enhanced community detection framework that improves communities detected by existing community detection methods. The framework introduces three noise methods to help detect communities better. Theoretical justification and extensive experiments on synthetic and real-world datasets show that our framework helps community detection methods find better communities.

• Information systems →Data mining;

Community Detection, Noise-Enhanced Methods, Graph Mining.

ACM Reference Format: Reyhaneh Abdolazimi, Shengmin Jin, and Reza Zafarani. 2020. Noise-Enhanced Community Detection. In Proceedings of the 31st ACM Conference on Hypertext and Social Media (HT ’20), July 13–15, 2020, Virtual Event, USA. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3372923.3404788

Communities are observed in many real-world networks: sets of nodes with higher internal density within each set than between them [6]. Communities carry various insights. In biological networks, communities represent functional units of cells [38]; in scientific collaboration networks, communities denote scientists with similar research interests [36]; and in social networks, communities are groups of friends with similar interests or backgrounds [11]. To detect communities more accurately and efficiently in networks, research has focused on designing new community detection algorithms [3, 6, 11, 28, 29, 35, 37]. Instead of designing new algorithms, an unexplored alternative to improve communities detected is to modify the input data to such algorithms: the network.

Communities are observed in many real-world networks: sets of nodes with higher internal density within each set than between them [6]. Communities carry various insights. In biological networks, communities represent functional units of cells [38]; in scientific collaboration networks, communities denote scientists with similar research interests [36]; and in social networks, communities are groups of friends with similar interests or backgrounds [11]. To detect communities more accurately and efficiently in networks, research has focused on designing new community detection algorithms [3, 6, 11, 28, 29, 35, 37]. Instead of designing new algorithms, an unexplored alternative to improve communities detected is to modify the input data to such algorithms: the network.

A natural approach to modify data is to introduce noise. While noise is often unwanted and uncontrollable, and attempts are made to remove or reduce its effects, it has been shown beneficial in many areas of science, especially in nonlinear information processing systems [5]. Noise enhancement has long been used in physical systems as stochastic resonance and has also shown promise in areas such as stochastic optimization, image processing, and machine learning [2, 5, 32, 34]. Such benefits of adding noise have motivated us to explore the possibility of enhancing community detection by adding noise. Adding noise introduces an extra step to the existing algorithms. This extra noise injection step introduces a degree of randomization to the algorithms. A natural way to introduce noise in a network is to add edges as it allows one to systematically compare the detected communities in noisy and noiseless networks. To provide some intuition on how adding noise can improve community detection, we provide an example. Consider the graph in Figure 1a with 10 nodes and 10 edges. In this graph, we can detect three communities (shown with ovals) using the Leading Eigenvector community detection method [29]: {1, 2, 3, 4}, {5, 6, 7}, and {8, 9, 10}. We can evaluate these communities using a community detection objective function. Here, we use edge cut [19] and obtain an edge cut value of 1.3. We add a single noise edge (3, 5) to the graph (the dashed line) to get the noisy graph in Figure 1b. The same Leading Eigenvector method now detects two communities in this noisy graph: {1, 2, 3, 4, 5} and {6, 7, 8, 9, 10}. The added noise not only leads to finding fewer communities but also better ones, as the edge cut value for these new communities in the original graph is 1, a %30 decrease over the initial value of 1.3.

Noise-Enhanced Community Detection. In this paper, we investigate noise-enhanced community detection. We propose a simple framework to improve communities in an undirected unweighted network by adding noise, as outlined in Algorithm 1. Our approach is iterative (to account for noise randomness). In each iteration,

we build a noisy network by adding noise (edges) to the original graph, and we detect communities in this noisy network. We then evaluate the communities detected in the original graph using some objective function. We iterate a few times and return the best communities detected, e.g., with the highest objective function value, as the noise-enhanced communities. Compared to communities detected in the original graph, our goal is to detect better communities (in terms of some objective function) while injecting limited noise, i.e., without significantly increasing the community detection execution time. Overall, we aim to answer two questions:

Q1. Does adding noise improve the performance of community detection algorithms? If it does, to what extent injecting noise will improve detected communities?

Q2. Injecting noise increases the cost of finding communities. Are the improvements justifiable relative to the potential improvements to detect communities? What is the trade-off?

By addressing these questions, at a high level, our framework makes the following contributions:

• We introduce noise-enhanced community detection, a framework to improve current community detection methods by introducing noise;

• We introduce three methods to add noise to a graph. These methods can be used as a preprocessing step to improve existing community detection algorithms (Section 3);

• We provide a theoretical foundation for noise-enhanced community detection by proving that the suggested noise injection methods improve common community detection objective functions under different scenarios (Section 5); and

• We evaluate our framework on various real-world and synthetic networks using well-established community detection methods. Our results show that adding noise to networks allows one to detect better communities compared to those detected in the original graphs (Section 6).

While to the best of our knowledge, there has been no attempts to enhance community detection by adding noise, our framework broadly relates to research on (I) community detection and (II) noise-enhanced systems.

Community Detection. There are many techniques to detect communities in networks. Here, we focus on the more common community detection methods and group them into the following four categories (refer to Ref. [8] for a comprehensive review).

I. Hierarchical methods are suitable for networks with hierarchical structure, and can be grouped into: (1) agglomerative and (2) divisive methods [8]. Agglomerative methods iteratively merge communities with sufficiently high similarity and divisive algorithms iteratively split communities by removing edges that connect vertices with low similarity. A well-known divisive algorithm is the one proposed by Girvan and Newman [31], which splits communities by computing edge betweenness. The algorithm is computationally expensive, and cannot be applied to large networks. A well-known agglomerative method is FastGreedy, which iteratively merges groups of nodes by using a greedy technique [28]

II. Modularity-based methods optimize modularity, a community quality measure, to obtain better communities [8]. These methods mostly belong to one of four categories: (1) greedy methods [28], or those that are based on (2) simulated annealing [12], (3) extremal optimization [7], or (4) spectral optimization [29]. A fast greedy method from this category is the Louvain method [3], which hierarchically optimizes modularity.

III. Spectral methods rely on the rich foundation in spectral graph theory to detect communities [8]. A well-known example is the Leading Eigenvector method [29], which using spectral bisection splits a network into groups while minimizing edges between them.

IV. Dynamic methods detect communities by running a dynamical process on the network. These algorithms are mostly based on random walks [35], spin dynamics [39], or synchronization [1]. WalkTrap [35], a popular method from this category, relies on random walks to compute similarities between nodes, which in turn are used to detect communities via hierarchical clustering.

As our goal is to add an extra noise injection step to the community detection process, we experiment with well-known representatives from each community detection category as we will detail in our experiments.

Noise-Enhanced Systems. Adding noise enhances performance in many areas [5]. We review some here.

I. Stochastic Resonance (SR) is observed when increasing random noise improves signal detection performance [22]. SR is frequently used in noise-enhanced information systems with examples in biological, physical, and engineered systems [10, 23, 24].

II. Image Processing also benefits from noise enhancement. Adding noise to images before thresholding can improve the human brain’s ability to perceive noisy visual patterns [42]. Adding noise can also improve image segmentation [16], image re-sampling detection [26], and image resizing detection [25]. As an example, adding an appropriate amount of noise can result in more accurate detection

of micro-calcifications in mammograms, which in turn can lead to early breast cancer diagnosis [44].

III. Signal Detection. Noise can help improve the detectability of signals. For example, when detecting a constant signal in a Gaussian mixture noise background, some white Gaussian noise can improve the performance of the sign detector [15]. Additive noise can also help detect a weak sinusoid signal more efficiently [46].

IV. Optimization. In search algorithms, when searching for an optimum is likely to get trapped in local minima, randomization helps finding optimal or near-optimal solutions. For example, the randomization in both crossover and mutation steps of Genetic Algorithms (GA) [43] helps avoid self-similarity in the population, i.e., helps avoid local minima [5]. The role of mutation is similar to adding noise and often a suitable mutation rate can improve performance.

V. Machine Learning. Noise can help reduce the convergence time in many clustering and competitive learning algorithms [32]. It can also decrease the convergence time of backpropagation algorithm, when training convolutional neural network [2]. This happens as backpropagation and some clustering algorithms such as 𝑘-means can be thought of as special cases of Expectation-Maximization (EM) algorithm [33], which improves by adding noise.

According to Algorithm 1, our framework follows three steps: first, some noisy edges are added to the graph. Then, communities are identified in the noisy graph using a community detection algorithm. Finally, the detected communities are evaluated using an objective function. Note that the objective function is evaluated on the original graph instead of the noisy graph to determine improvements due to noise (line 10 in Algorithm 1). To systematically analyze noise enhancement in community detection, we experiment with various community detection methods and objective functions. To add noise to graphs, we introduce three general ways. Our noise injection methods focus on high degree nodes. In Section 5, we theoretically justify this decision where we show the importance of [disconnected] high degree nodes in detecting communities. Furthermore, empirical findings have shown that communities are more likely to contain more high degree nodes [27]. Informally, our results show that if a high degree node is not connected to another high degree node, by connecting it, we strengthen the within-community connections, and make it easier for community detection algorithms to detect the communities. Therefore, in the proposed noise methods, we perform the following common steps: (1) we sort nodes based on their degrees, (2) we select the top 𝑝percent of sorted nodes as candidates, and (3) we add edges within candidates if those edges do not exist. To add edges, we select pairs of nodes (edge endpoints) from candidates. The proposed methods vary in how such pairs of nodes are selected.

I. Random Noise (Random). Edge endpoints are randomly chosen from the candidates. Before adding a noise edge, we ensure that it is not in the graph. If the number of candidates equals the number of nodes, Random simply connects nodes irrespective of their degrees.

II. Weighted Noise (Weighted). We select node (edge endpoint) 𝑣𝑖with probability 𝑃Weighted(𝑣𝑖) that depends on its degree and that of other candidate nodes:

𝑃Weighted(𝑣𝑖) = 𝑑𝑖 Í𝑛 𝑗=1 𝑑𝑗 ,

where 𝑑𝑖denotes the degree of node 𝑣𝑖, and 𝑛is the number of candidate nodes.

III. Frequency Noise (Frequency). Nodes are selected based on the degree distribution of the candidates, where nodes whose degrees are more frequent, are less likely to be selected:

𝑃Frequency(𝑣𝑖) = 1 −𝑓𝑑𝑖/𝑛

𝑓𝑑𝑖× Í𝑘 𝑑=1(1 −𝑓𝑑/𝑛) , (1)

where 𝑓𝑑𝑖is the frequency of degree 𝑑inside candidates and 𝑘is the maximum degree.

Time Complexity. The proposed noise methods include the following steps in a graph with |𝑉| nodes and |𝐸| edges: Computing node degrees in 𝑂(|𝐸|), sorting nodes based on their degrees in 𝑂(|𝑉| log |𝑉|), selecting candidates in 𝑂(1), calculating node probabilities in 𝑂(|𝑉|), and adding noise edges based on node probabilities in 𝑂(|𝐸|) (The number of noise edges is at most |𝐸|). So, the final time complexity introduced by adding noise is 𝑂(|𝑉| log |𝑉|).

III. Frequency. Nodes with less frequent degrees in candidates are more probable to be selected. Hence, edge (𝑎,𝑐) is the most likely noise edge as nodes 𝑎, and 𝑐with degrees 4 and 3 and 𝑓4 = 𝑓3 = 1 have the highest probability 𝑃Frequency(𝑎) = 𝑃Frequency(𝑐) = 3/8 to be chosen. The frequency of other candidate nodes are as follows: 𝑃Frequency(𝑑) = 𝑃Frequency(𝑓) = 1/8.

In this section, we detail the datasets, how noise quantity was controlled, candidates sizes selected, Q1 community detection methods used, objective functions, and evaluation metrics.

I. Datasets. We study the impact of noise on community detection in both synthetic and real-world networks:

(1) Synthetic Networks. To systematically verify our noise-enhanced framework, we should be able to analyze it in networks with different community structures. So, we use the well-established benchmark [17] proposed by Lancichinetti et al., which generates graphs with different degree distributions and community sizes distributions. To create such benchmark graphs, we need to set the value of several parameters, where we specifically followed suggestions provided by [17] and created 32 datasets. The parameters are in Table 2, where 𝑛is the number of nodes, 𝛾is the exponent of the

power law degree distribution, 𝛽is the exponent of the power law distribution for community sizes, 𝜇is the mixing parameter where 1−𝜇determines the fraction of links that each node shares with the other nodes in its community, and 𝐾is the average node degree.

(2) Real-world Networks: We also evaluate our framework with

real-world networks. For systematic analysis, we use 13 real-world networks from four general category of networks: biological networks, collaboration networks, social networks, and road networks. Table 1 provides the statistics of these real-world networks.

II. Noise Proportion. We characterize noise in terms of the proportion of noise edges added, where noise increases the number of edges in the graph by 𝑒percent. For example, if there are 1,000 edges in the graph, we can add 2% of current edges (20 edges) to the graph. We vary 𝑒values from 1% to 10% with 1% increments.

III. Candidates Size. As noted in Section 3, we select the top 𝑝percent of sorted nodes as candidates. We vary 𝑝values from 10% to 100% with 10% increments. When 𝑝= 100%, all nodes are candidates.

IV. Community Detection Methods. Based on the review in Section 2, we select four algorithms, each representing a category of community detection methods: (1) FastGreedy from hierarchical methods, (2) Louvain from modularity-based methods, (3) Leading EigenVector from spectral methods, and (4) Walktrap from dynamic methods. All selected methods have shown great performance in extracting high quality communities.

V. Objective Functions. There are two groups of objectives functions for evaluating quality of communities (see Ref. [19] for details): (1) multi-criterion scores, which consider both edges inside the communities and those crossing communities, and (2) single criterion scores, which either consider inside edges, or crossing edges. To evaluate the quality of communities, we select two objective functions from each of the aforementioned categories; conductance [14, 41] and normalized cut [41] from multi-criterion scores, modularity [30] and edge cut [19] from single criterion scores.

VI. Evaluation Metrics. To assess noise enhancement, we measure the following for each objective function: • Expected First Success (EFS) is the expected number of times (Iterations in Algorithm 1) that we need to add noise to the network to ensure that we improve communities at least once. For example, if we run Algorithm 1 for 100 iterations and improve communities in 34 of these iterations, the Expected First Success is 3 as 100

34 ≃2.94. Formally, for objective function 𝑜𝑏𝑗:

EFS𝑜𝑏𝑗=  number of iterations



noise-enhanced iterations

• Relative Objective Improvement (ROI) is the relative objective value improvement after adding noise:

ROI𝑜𝑏𝑗= 𝑜𝑏𝑗noise-enhanced −𝑜𝑏𝑗original

𝑜𝑏𝑗original × 100

Before performing experiments, we show that these objective functions can in theory be improved next.

In this section, we theoretically analyze noise-enhancement benefits in community detection. We demonstrate that (1) adding a noise edge between two high degree nodes will increase the chance of re-partitioning a graph by assigning the two high degree nodes to the same community in terms of the minimum normalized cut, for which we provide a spectral analysis. As a result, we show that (2) once a high degree node moves to the community of the other, all objective functions in this study improve under some constraints. Our setting can be generalized to multiple communities and multiple nodes in these communities.

5.1 Spectral Analysis

5.2 Objective Function Analysis

To simplify, consider graph 𝐺with communities 𝑆1 and 𝑆2. Denote disconnected high degrees node 𝑣𝑖in 𝑆1 with degree 𝑑𝑖and 𝑣𝑗 in 𝑆2 with degree 𝑑𝑗. Assume 𝑑𝑖= 𝑑𝑖,𝑖𝑛+ 𝑑𝑖,𝑜𝑢𝑡(similarly, 𝑑𝑗= 𝑑𝑗,𝑖𝑛+ 𝑑𝑗,𝑜𝑢𝑡), where 𝑑𝑖,𝑖𝑛(𝑑𝑗,𝑖𝑛) is the number of edges between 𝑣𝑖(𝑣𝑗) and nodes in 𝑆1 (𝑆2), and 𝑑𝑖,𝑜𝑢𝑡(𝑑𝑗,𝑜𝑢𝑡) is the number of edges between 𝑣𝑖(𝑣𝑗) and nodes in 𝑆2 (𝑆1). Let 𝑚𝑆2 denotes the number of edges in 𝑆2, and 𝑚𝑆1 the number of edges in 𝑆1. We use prime symbol (′) to denote the updated objective function value, e.g.,𝑐𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒′. We assume that the high degree node that moves to the community of the other is the one that has comparatively less within-community connections than cross-community connections, e.g., 𝑣𝑖moves to 𝑆2 when 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡. We show that all objective functions can be improved under this condition. Theorem 5.2 (Modularity Change). If 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡, moving 𝑣𝑖 from 𝑆1 to 𝑆2 increases modularity.

Proof. Modularity [30] measures the density of edges inside communities compared to edges between communities, and can be

2𝑚 Í 𝑖𝑗[𝐴𝑖𝑗−𝑑𝑖𝑑𝑗

obtained by 1

2𝑚]𝛿(𝑐𝑖,𝑐𝑗), where 𝐴is the adjacency matrix of graph 𝐺, 𝑑𝑖and 𝑑𝑗are degrees of nodes 𝑖and 𝑗, 𝑚is the number of edges in the graph, and 𝛿(𝑐𝑖,𝑐𝑗) = 1 if both vertices 𝑖 and 𝑗belong to the same community; otherwise, it is 0. If 𝑣𝑖moves to 𝑆2, the modularity of each community changes as follows: (1) 𝑆2: the modularity of 𝑣𝑖’s neighbors in 𝑆2 will increase from zero to a

positive value 1−𝑑𝑖𝑑𝑗

2𝑚as the delta function now becomes 𝛿(𝑐𝑖,𝑐𝑗) = 1 for all such neighbors 𝑗. On the other hand, the modularity of nodes that are not connected to 𝑣𝑖changes from zero to negative values −𝑑𝑖𝑑𝑗

2𝑚. When 𝑑𝑖,𝑜𝑢𝑡> 𝑚𝑆2, the overall modularity of nodes in 𝑆2 will be increased. (2) 𝑆1: the modularity of nodes which are connected to 𝑣𝑖will be decreased (positive values are changed to zero), but modularity of nodes that were not connected to 𝑣𝑖are increased (negative values are changed to zero). When 𝑑𝑖,𝑖𝑛< 𝑚𝑆1, the modularity of nodes in 𝑆1 will be increased. Since adding 𝑣𝑖to 𝑆2 only affects the modularity of 𝑆1 and 𝑆2, and they are increased, the overall modularity of G will be also increased. □ Theorem 5.3 (Edge cut Change). If 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡, moving 𝑣𝑖from 𝑆1 to 𝑆2 decreases edge cut.

Proof. Edge cut, 𝑐𝑆, is the number of crossing edges between community 𝑆and other nodes in 𝐺[19]. As we only consider 𝑆1 and 𝑆2, 𝑐𝑆1 = 𝑐𝑆2, which we simplify as 𝑐𝑆. If we move 𝑣𝑖to 𝑆2, 𝑑𝑖,𝑜𝑢𝑡edges will be counted as edges in 𝑆2, and 𝑑𝑖,𝑖𝑛edges will be considered as new crossing edges between 𝑆1 and 𝑆2. So, the new edge cut values are𝑐′ 𝑆1 = 𝑐′ 𝑆2 = 𝑐𝑆−𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛. When𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡, edge cut is decreased. □

Theorem 5.4 (Conductance Change). If 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡, moving 𝑣𝑖 from 𝑆1 to 𝑆2 decreases conductance.

Proof. Conductance for community 𝑆can be calculated as: 𝐶𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒𝑆= 𝑐𝑠

2𝑚𝑠+𝑐𝑠[14, 41]. If we move 𝑣𝑖to 𝑆2, 𝑑𝑖,𝑜𝑢𝑡edges

Figure 3: Modularity of noise-enhanced Leading EigenVector on Bio-Dmela dataset when using frequency noise and with candidates size 𝑝∈{40%, 80%, 100%}.

𝑚𝑆1 −𝑑𝑖,𝑖𝑛. So, 𝐶𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒′ 𝑆2 = 𝑐′ 𝑆2

2𝑚′ 𝑆2+𝑐′ 𝑆2 = 𝑐𝑆−𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛

2𝑚𝑆2+𝑐𝑆+𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛and

𝐶𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒′ 𝑆1 = 𝑐′ 𝑆1

2𝑚′ 𝑆1+𝑐′ 𝑆1 = 𝑐𝑆−𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛

2𝑚𝑆1+𝑐𝑆+𝑑𝑖,𝑜𝑢𝑡−𝑑𝑖,𝑖𝑛. When𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡,

conductances of 𝑆1 and 𝑆2 will decrease. □

Theorem 5.5 (Normalized Cut Change). If 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡, moving 𝑣𝑖from 𝑆1 to 𝑆2 decreases cut size.

Proof. Normalized cut (Ncut) for community𝑆can be calculated as 𝑁𝑐𝑢𝑡𝑆= 𝑐𝑠

2(𝑚−𝑚𝑠)+𝑐𝑠[41]. The first term is basically conductance, and conductance is decreased based on Theorem 5.4.

2𝑚𝑠+𝑐𝑠+ 𝑐𝑠

So, 𝑁𝑐𝑢𝑡′ 𝑆2 = 𝑐′ 𝑆2

2𝑚′ 𝑆2+𝑐′ 𝑆2 + 𝑐′ 𝑆2

2(𝑚−𝑚′ 𝑆2)+𝑐′ 𝑆2 = 𝐶𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒′ 𝑆2+

2(𝑚−𝑚𝑆2)+𝑐𝑆2−3𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛, and 𝑁𝑐𝑢𝑡′ 𝑆1 = 𝑐′ 𝑆1

𝑐𝑆2−𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛

2𝑚′ 𝑆1+𝑐′ 𝑆1 +

𝑐′ 𝑆1

2(𝑚−𝑚′ 𝑆1)+𝑐′ 𝑆1 = 𝐶𝑜𝑛𝑑𝑢𝑐𝑡𝑎𝑛𝑐𝑒′ 𝑆1 + 𝑐𝑆1−𝑑𝑖,𝑜𝑢𝑡+𝑑𝑖,𝑖𝑛

2(𝑚−𝑚𝑆1)+𝑐𝑆1−𝑑𝑖,𝑜𝑢𝑡+3𝑑𝑖,𝑖𝑛. Hence, when

𝑘𝑑𝑖,𝑜𝑢𝑡< 𝑑𝑖,𝑖𝑛< 𝑑𝑖,𝑜𝑢𝑡and 1/3 ≤𝑘< 1, Ncut for 𝑆1 decreases. □

We evaluate the impact of adding noise on communities detected in real-world and synthetic networks.

6.1 Noise-enhanced Community Detection in Real-World Networks.

We start with an example. Figure 3 shows the modularity of noiseenhanced Leading EigenVector method on Bio-Dmela dataset using Frequency method for various candidate sizes,𝑝∈{40%, 80%, 100%}, and noise proportions 𝑒. For stability, for each 𝑒, we run the experiments 10 times and compute the average modularity value. Error bars denote one standard deviation. The dashed horizontal red line shows the original modularity obtained in the noiseless Bio-Dmlea. As shown, most obtained modularity values are above the original modularity in the noiseless graph, implying that better communities are found with respect to modularity by adding noise. Figure 3 demonstrates the feasibility of noise-enhanced community detection. Hence, we further design experiments to systematically assess the impact of noise on all graphs. For each graph

and each candidate size 𝑝, we use noise methods to add different proportions of noise 𝑒and measure our evaluation metrics (EFS and ROI) for all objective functions and community detection methods. For each 𝑒, we run the experiments 10 times to assess stability of the results. As 𝑝varies from 10% to 100% with 10% increments and 𝑒varies from 1% to 10% with 1% increments, for each 𝑝, we perform 100 experiments, and for all 𝑝, we perform 1, 000 experiments. For each dataset and objective function, these results with respect to both evaluation metrics (ROI and EFS) can be summarized using 6 plots as shown as an example in Figure 4. The figure shows the effect of all three proposed noise methods on conductance of communities detected in HepPH. As shown in the Figure, EFS is on average 2 for Louvain, FastGreedy, and Leading Eigenvector community detection methods, so on average, one only needs to add noise twice to improve detected communities. ROI for conductance is also shown in Figure 4. As all these noised-enhanced methods can improve conductance (negative ROI value), for clarity, we show the absolute values of ROI in the figure. We observe that the conductance of communities detected by Leading Eigenvector is much higher than that of those detected by other methods. Overall, our experiments lead to 13×3×4 = 156 figures for all datasets, community detection methods, noise methods, and objective functions.

For space reasons, we summarize our results in Table 3, which provides the average EFS and ROI of noise-enhanced community detection methods on all real-world networks. For each network, there are four rows, one for each objective function. For a given data set, noise method, and community detection method, we provide both EFS and ROI. Positive ROI values for modularity indicate improvements (better communities) and negative ROI values for conductance, edge cut, and normalized cut indicate improvements. Gray cells indicate that the specific community detection method did not improve with the specific noise method, and pink cells indicate that the community detection method was unable to identify communities (often due to computational complexity). We summarize the findings in Table 3 as follows:

• Noise-enhanced community detection obtains an average EFS = 43 and ROI = 10.5 (absolute ROI values are considered for calculating the averages) over all networks, community detection methods, noise methods, and objective functions, indicating that noise often improves detected communities; • Weighted Noise is the best noise method for improving communities in biological networks, social networks, and collaboration networks, and Random Noise is the best choice for road networks; • Louvain methods improves the most by adding noise compared to other community detection methods; • While all community detection method in general improve, each method improves best with a specific type of noise: (1) Louvain improves more with Weighted Noise and Frequency Noise, where for Weighted: (EFS = 21, ROI = 3.45), and for Frequency: (EFS = 29, ROI = 5.3). These numbers are the average [absolute] values for modularity, conductance, edge cut, and normalized cut; (2) Leading EigenVector improves more with Random Noise and Weighted Noise, where for Random: (EFS = 25, ROI = 27.2), and for Weighted: (EFS = 37, ROI = 31.4); (3) Fastgreedy improves more with Weighted Noise and Frequency Noise, where for Weighted: (EFS = 29, ROI = 5.05), and for Frequency: (EFS =

Random

20

80

15

60

Figure 4: Effect of all three proposed noise methods on the conductance of communities detected in HepPH. The first and the second row show EFS and ROI for conductance. For HepPH, EFS=2 on average for Louvain, FastGreedy, and Leading Eigenvector and ROI of communities detected by Leading Eigenvector is much higher than that of those detected by other methods.

40, ROI = 6.5); and (4) WalkTrap improves best with Random Noise, where for Random: (EFS = 40, ROI = 5.05); and • Adding noise often cannot help detect better communities in road networks. This happens as there are not as many high degree nodes in road networks as there are in other types of networks, where the proposed noise methods rely on high degree nodes.

Based on results obtained in Section 5.1, we also added a constraint when selecting candidates where we enforced the degree of each node among candidates to be higher than the average degree of its neighbors. Then we sort nodes in candidates based on their degrees and add noise edges by connecting pairs of candidates. Table 4 shows the average EFS and ROI of adding this new constraint to our noise enhanced community detection methods on 4 real-world datasets (for each category in Table 1, one dataset is chosen). As the results are similar to the results in Table 3 and connecting nodes with high degrees is easier to implement, the results following are based on connecting high degree nodes.

Impact of Limited Noise. We note that our experiments show that even when we add a few edges to large networks, one can detect better communities. As an example, EFS and ROI for modularity after adding 1, 000 edges to Facebook-Company network is shown in Table 5. The Table shows that if we use any of Louvain, FastGreedy, or Leading EigenVector methods where noise is on average added four times to this dataset (EFS=4), we can detect better communities: ROI value will be at least %0.23.

Weighted

Frequency

10

8

6

6.2 Noise-enhanced Community Detection in Synthetic networks.

We start with an example. Figures 5 and 6 provide the EFS of modularity and edge cut after applying Louvain on synthetic networks with 𝑛= 1, 000 nodes and 𝑛= 10, 000 nodes, respectively. The points with EFS> 100 are shown at the top of the charts. As Figure 5 shows, when 𝜇= 0.5 (a balance between number of edges inside communities and outside of them), Louvain is able to improve modularity with low values of EFS, while when 𝜇= 0.1, as 90% of edges are inside communities and our approach is based on adding noise edges, Louvain is less likely to improve modularity. This figure shows when graphs become denser (increasing 𝐾), EFS for edge cut increases. Figure 6 shows when graphs become larger (𝑛= 10, 000) and denser (increasing 𝐾), EFS for modularity decreases on average. All charts in both Figures 5 and 6 show that noise enhanced Louvain is able to highly improve modularity and edge cut EFS for synthetic networks with 𝜇= 0.5, 𝛽= 1, and 𝛾= 2. Table 6 provides the average of EFS and ROI for synthetic networks. The first and second four rows show statistics on objective functions for 𝑛= 1, 000 and 𝑛= 10, 000, respectively. Each element in Table 6 shows the average EFS or ROI for 16 synthetic networks with the same number of nodes (𝑁) and different 𝜇, 𝛽, and𝛾values. As Table 6 shows noise-enhanced community detection is able to improve all objective functions in terms of both EFS and ROI. WalkTrap

Table 3: Expected First Success (EFS) and Relative Objective Improvement (ROI) of noise-enhanced community detection methods on real-world networks. These numbers show that: (1) Louvain improves more with Weighted Noise and Frequency Noise, (2) Leading EigenVector improves more with Random Noise and Weighted Noise, (3) FastGreedy improves more with Weighted Noise and Frequency Noise, and (4) WalkTrap improves best with Random Noise.

often does not highly improve when adding noise to large graphs, especially for modularity objective function.

6.3 Ground-truth Communities

We introduced a framework to enhance community detection by adding noise to networks. The approach adds a preprocessing step to the current community detection methods as a noise injection step. For noise injection, three methods were proposed that randomly add noise edges to the network, focusing on high degree nodes. Our theoretical and extensive empirical results show that this approach leads to finding better communities using current community detection methods not only by detecting communities that are better in terms of an objective functions but also by detecting communities that are more similar to the ground-truth.

[10] Luca Gammaitoni, Peter Hänggi, Peter Jung, and Fabio Marchesoni. 1998. Stochastic resonance. Reviews of modern physics 70, 1 (1998), 223. [11] Michelle Girvan and Mark EJ Newman. 2002. Community structure in social and biological networks. PNAS 99, 12 (2002). [12] Roger Guimerà, Marta Sales-Pardo, and Luís A. Nunes Amaral. 2004. Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E 70 (Aug 2004), 4. Issue 2. [13] Shengmin Jin and Reza Zafarani. 2020. The Spectral Zoo of Networks: Embedding and Visualizing Networks with Spectral Moments. In Proceedings of the KDD.

[1] Alex Arenas, Albert Díaz-Guilera, and Conrad J Pérez-Vicente. 2006. Synchronization reveals topological scales in complex networks. Phys. Rev. letters 96, 11 (2006). [2] Kartik Audhkhasi, Osonde Osoba, and Bart Kosko. 2016. Noise-enhanced convolutional neural networks. Neural Networks 78 (2016), 15–23. [3] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. JSTAT 2008, 10 (2008), P10008. [4] Jeff Cheeger. 1969. A lower bound for the smallest eigenvalue of the Laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner. 195–199.

[5] Hao Chen, Lav R Varshney, and Pramod K Varshney. 2014. Noise-enhanced information systems. PIEEE (2014). [6] Aaron Clauset, Mark EJ Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Phys. Rev. E 70, 6 (2004), 066111. [7] Jordi Duch and Alex Arenas. 2005. Community detection in complex networks using extremal optimization. Phys. Rev. E 72 (Aug 2005), 027104. Issue 2. [8] Santo Fortunato. 2010. Community detection in graphs. Physics reports 486, 3-5 (2010), 75–174. [9] Santo Fortunato and Marc Barthelemy. 2007. Resolution limit in community detection. Proceedings of the national academy of sciences 104, 1 (2007), 36–41.

[10] Luca Gammaitoni, Peter Hänggi, Peter Jung, and Fabio Marchesoni. 1998. Stochastic resonance. Reviews of modern physics 70, 1 (1998), 223. [11] Michelle Girvan and Mark EJ Newman. 2002. Community structure in social and biological networks. PNAS 99, 12 (2002). [12] Roger Guimerà, Marta Sales-Pardo, and Luís A. Nunes Amaral. 2004. Modularity from fluctuations in random graphs and complex networks. Phys. Rev. E 70 (Aug 2004), 4. Issue 2. [13] Shengmin Jin and Reza Zafarani. 2020. The Spectral Zoo of Networks: Embedding and Visualizing Networks with Spectral Moments. In Proceedings of the KDD.

[14] Ravi Kannan, Santosh Vempala, and Adrian Vetta. 2004. On clusterings: Good, bad and spectral. JACM 51, 3 (2004). [15] Steven Kay. 2000. Can detectability be improved by adding noise? IEEE signal processing letters 7, 1 (2000), 8–10. [16] O. Krishna, R. K. Jha, A. K. Tiwari, and B. Soni. 2013. Noise induced segmentation of noisy color image. In 2013 NCC. 1–5. [17] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 4 (2008), 046110. [18] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. [19] Jure Leskovec, Kevin J Lang, and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proc. of WWW. 631–640. [20] Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. 2005. On trip planning queries in spatial databases. In SSTD. 273–290. [21] Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. 2017. Estimating mixed memberships with sharp eigenvector deviations. arXiv preprint arXiv:1709.00407 (2017). [22] Mark D McDonnell and Derek Abbott. 2009. What is stochastic resonance? Definitions, misconceptions, debates, and its relevance to biology. PLoS comp. bio. 5, 5 (2009). [23] Mark D McDonnell and Lawrence M Ward. 2011. The benefits of noise in neural systems: bridging theory and experiment. Nature Reviews Neuroscience 12, 7 (2011), 415. [24] Frank Moss, Lawrence M Ward, and Walter G Sannita. 2004. Stochastic resonance and sensory information processing: a tutorial and review of application. Clinical neurophysiology 115, 2 (2004), 267–281. [25] L. Nataraj, A. Sarkar, and B. S. Manjunath. 2009. Adding Gaussian noise to “denoise” JPEG for detecting image resizing. In ICIP. 1493–1496. [26] Lakshmanan Nataraj, Anindya Sarkar, and Bangalore S Manjunath. 2010. Improving re-sampling detection by adding noise. In Media Forensics and Security II, Vol. 7541. [27] Mark Newman. 2018. Networks. Oxford university press. [28] Mark EJ Newman. 2004. Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 6 (2004). [29] Mark EJ Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 3 (2006), 036104. [30] Mark EJ Newman. 2006. Modularity and community structure in networks. PNAS 103, 23 (2006), 8577–8582. [31] Mark EJ Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 2 (2004), 026113. [32] Osonde Osoba and Bart Kosko. 2013. Noise-enhanced clustering and competitive learning algorithms. Neural Networks 37 (2013), 132–140. [33] Osonde Osoba, Sanya Mitaim, and Bart Kosko. 2013. The noisy expectation– maximization algorithm. Fluctuation and Noise Letters 12, 03 (2013), 1350012. [34] Renbin Peng, Hao Chen, and Pramod K Varshney. 2009. Noise-enhanced detection of micro-calcifications in digital mammograms. IEEE JSTSP 3, 1 (2009), 62–73. [35] Pascal Pons and Matthieu Latapy. 2005. Computing communities in large networks using random walks. In ISCIS. [36] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. 2004. Defining and identifying communities in networks. PNAS 101, 9 (2004). [37] Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3 (2007). [38] Erzsébet Ravasz, Anna Lisa Somera, Dale A Mongru, Zoltán N Oltvai, and A-L Barabási. 2002. Hierarchical organization of modularity in metabolic networks. science 297, 5586 (2002), 1551–1555. [39] Jörg Reichardt and Stefan Bornholdt. 2006. Statistical mechanics of community detection. Phys. Rev. E 74, 1 (2006), 016110. [40] Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. [41] Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. Departmental Papers (CIS) (2000), 107. [42] Enrico Simonotto, Massimo Riani, Charles Seife, Mark Roberts, Jennifer Twitty, and Frank Moss. 1997. Visual Perception of Stochastic Resonance. Phys. Rev. Lett. 78 (Feb 1997), 0. Issue 6. [43] Kit-Sang Tang, Kim-Fung Man, Sam Kwong, and Qun He. 1996. Genetic algorithms and their applications. IEEE signal processing magazine 13, 6 (1996), 22–37. [44] Ted C Wang and Nicolaos B Karayiannis. 1998. Detection of microcalcifications in digital mammograms using wavelets. IEEE trans. on medical imaging 17, 4 (1998). [45] R. Zafarani and H. Liu. 2009. Social Computing Data Repository. http:// socialcomputing.asu.edu [46] Steeve Zozor and Pierre-Olivier Amblard. 2002. On the use of stochastic resonance in sine detection. Signal Proc. 82, 3 (2002).