# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### Heuristic but Fast
Subsequently, the authors of [21] proposed the following measure to compute the quality of a community \(C\):  
\[q(C)=\frac{|E_{C}^{out}|+r(C)}{|E_{C}^{in}|}. \tag{1}\]  
Furthermore, given a set of communities \(\mathbf{C}=\{C_{1},\ldots,C_{k}\}\), the quality of the partition \(\mathbf{C}\) is defined as follows:  
\[q_{G}^{\mathbf{C}}=\sum_{C\in\mathbf{C}}q(C). \tag{2}\]  
Note that the quality of the partition \(\mathbf{C}\) increases as \(q_{G}^{\mathbf{C}}\) decreases. More specifically, the proposed community quality measure determines the quality of a community \(C\) by minimizing the sum of the following two terms: \(\frac{|E_{C}^{out}|}{|E_{C}^{in}|}\) and \(\frac{r(C)}{|E_{C}^{in}|}\). As minimizing the number of outer edges while simultaneously maximizing the number of inner edges naturally leads to enhancing the quality of community structures, reducing the radius yields a similar outcome. Recall the significant role of the vertex's degree in controlling and stimulating neighboring nodes due to high-degree vertices' capability to impose distinct attributes on surrounding nodes [29]. Specifically, many (complex) networks exhibit a small number of influential high-degree vertices, such as social media influencers, pivotal commodities in co-purchasing networks, or a high-degree processor in a distributed computing network. These high-degree vertices are typically surrounded by numerous lower-degree vertices [30; 31]. In such networks, each vertex is either directly connected to or only a few links away from a high-degree node. With this in mind, having communities with small radii breaks the task into finding influential nodes that are at a proper distance from each other, as it turned out in [21] that an appropriate distance between high-degree nodes results in the formation of well-isolated communities. For this, the proposed optimization algorithm works in such a way that, with the general goal of minimizing the quality measures (1) and (2), it first establishes a set of promising initial communities (Algorithm 1) that then get purified with a local search manner (Algorithm 2). Simply put, the first stage seeks the best \(\alpha\) value leading to well-separated communities formed surrounding the set of influential vertices \(P_{\alpha}\). Equivalently, the goal of this phase restricts the objective to finding authoritative nodes that are at the right distance from each other, letting them freely absorb other nodes into their territory. ```
Input: Graph \(G\). Output: Set of initial communities \(\mathbf{C}\) and the corresponding set of influential nodes. 1 for\(\alpha=2\)to diameter\((G)\)do
2 Establish \(P_{\alpha}=\{p_{1},p_{2},\ldots,p_{m}\}\);// based on Definition 1. 3\(\mathbf{C}_{\alpha}=\{C_{1}=\{p_{1}\},\ldots,C_{|P_{\alpha}|}=\{p_{m}\}\}\);
4 while\(\exists v\
ot\in\bigcup_{i=1}^{|P_{\alpha}|}C_{i}\)do
5 Assign \(\forall\in\mathbf{C}_{\alpha}\) to its closest community \(C_{i}\in\mathbf{C}_{\alpha}\);
6 Record \(\mathbf{C}_{\alpha}\) and the corresponding \(P_{\alpha}\) and \(q_{G}^{\mathbf{C}_{\alpha}}\);
7 Return a set of community \(\mathbf{C}\) and the corresponding set of influential nodes \(P\) associated with the minimum obtained quality value \(q_{G}^{\mathbf{C}}\);
```  
**Algorithm 1**Creating Initial Communities (CIC)  
The second phase, afterward, updates initial communities using a local search technique that iteratively selects a community, favoring worse quality values. It then greedily improves communities with one of three functions: _Merge_, _Split_, and _Swap_. While the _Merge_ function assesses merging a community \(C\) into neighbor communities for quality improvement, the _Split_ function checks if applying the CIC stage to the induced sub-graph \(G^{\prime}\) formed by \(C\) can divide \(C\) into separate communities that result in a better quality value. The _Swap_ function, on the other hand, optimizes node swaps between \(C\) and its neighbors.