# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### Heuristic but Fast  
This section reviews the two-stage heuristic optimization-based community detection algorithm proposed in [21], which involves optimizing a connectivity-based quality metric. We first revisit the requirements and definition of the suggested quality metric, then outline the optimization algorithm. Afterward, we develop some theoretical arguments contributing to a more comprehensive evaluation of the algorithm's validity across varying network sizes. What is worth noting about this fast yet accurate heuristic approach is our aim to (1) propose a systematic way to improve the complementary graph of the Max-Min Modularity and (2) obtain a high-quality initial solution for the exact optimization procedure that will be explained in Section 2.2. Let the _degree_ of a node and its set of neighbors be defined naturally. Additionally, the _inner_ and _outer edges_ of a community \(C\), denoted as \(E_{C}^{in}\) and \(E_{C}^{out}\), respectively, represent the edges with both endpoints and one endpoint within \(C\). We proceed to define the _influential nodes_, which can be envisioned as vertices endowed with authority and the capacity to control and affect other nodes, particularly in our context, shaping communities. As elucidated in [21], nodes with high degrees that maintain an appropriate distance from each other emerge as suitable candidates for such roles. The intuition comes from the fact that the degree of nodes can substantially reflect the importance of vertices within the network. A high-degree vertex influences its surroundings more than a low-degree vertex. This is because it can pass messages to multiple nearby vertices and impose various features and information on them. For instance, a high-degree vertex in a communication network can significantly impact the spread of data and messages, affecting the behavior of its neighbors and the overall dynamics of the network. Think of the effect of a high-degree byzantine faulty process in a distributed computing network. Definition 1 gives a more formal characterization of the influential nodes. **Definition 1** (Influential node). : _Let \(\alpha\in\{1,\ldots,diameter(G)\}\) be an integer and define \(P_{\alpha}\subseteq V\) as a sequence of nodes arranged in descending order according to their degrees, provided they are all at least a steps away from each other. \(P_{\alpha}\) is referred to as the influential nodes of \(G\) with respect to \(\alpha\)._  
Note that the influential node of a community is not necessarily unique. In such a case, the influential node will be randomly picked among the candidates. **Definition 2** (Neighboring communities). : _Two communities \(C\) and \(C^{\prime}\) are said to be neighbors if there exists an edge \((i,j)\in E\) connecting \(i\in C\) to \(j\in C^{\prime}\). In this case, we refer to both \(i\) and \(j\) as boundary vertices of \(C\) and \(C^{\prime}\), respectively. Let \(BV(C)\) denote the set of all boundary vertices of \(C\)._  
**Definition 3** (Distance to a community). : _The distance between a vertex \(j\
ot\in C\) and the community \(C\) is determined as the length of the shortest path from \(j\) to the influential node of \(C\)._  
**Definition 4** (Radius). : _The radius of a community \(C\), denoted by \(r(C)\), is the maximum distance from its influential node to other vertices within the community._  
The influence a particular node exerts on others is evidently correlated with the distance between them. Valuable insights into this relationship can be gleaned from studies such as [16; 28]. For instance, note the more significant impact that a high-degree node in a communication graph has on vertices connecting to it directly (distance = 1) than on those that are connected to it through several intermediaries (distance > 1). Consequently, it is natural to assume that a community with a small radius is likely to be more interactive and homogeneous.