# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### Heuristic but Fast
1\(q\gets q_{G}^{\mathbf{C}}\);
2\(q_{temp}\gets 0\);
3 Iteration \(\gets 1\);
4 while\(q\leq(1-\epsilon)q_{temp}\wedge\textit{Iteration}\leq k\)*do
5\(q_{temp}\gets q\);
6 select a community \(C\in\mathbf{C}\) with probability \(\frac{q(C)}{q_{G}^{\mathbf{C}}}\);
7\((\mathbf{C},P)\leftarrow\) BestMovement(\(C\), \(\mathbf{C}\), \(P\));
8\(q\gets q_{G}^{\mathbf{C}}\);
9 Iteration++;
10 Return\((\mathbf{C})\);
11
12 Functions declaration:
13 BestMovement\((C,\mathbf{C},P)\)
14\((\mathbf{C}_{temp\_M},\textit{Ptemp\_M})\leftarrow\textit{Merge}(C,\mathbf{C},P)\);
15\((\mathbf{C}_{temp\_S},\textit{Ptemp\_S})\gets Split(C,\mathbf{C},P)\);
16\((\mathbf{C}_{temp\_Sw},\textit{Ptemp\_Sw})\gets Swap(C,\mathbf{C},P)\);
17 Among the returned partitions, retrieve the best set of communities \(\mathbf{C}\) corresponding to the minimum obtained quality value alongside its set of influential vertices \(P\);
18 Return\((\mathbf{C},P)\);
19 Merge\((C,\mathbf{C},P)\)
20 forevery\(C^{\prime}\in\mathbf{C}-C\) such that \(C^{\prime}\) is a neighbor community for \(C\)do
21 merge \(C\) and \(C^{\prime}\);
22 update and remember \(\mathbf{C}\) and also the set of influential vertices;
23 retrieve the set of communities \(\mathbf{C}\) and its set of influential vertices \(P\), corresponding to the minimum obtained quality value;
24 Return\((\mathbf{C},P)\);
25 Split\((C,\mathbf{C},P)\)
26\(IG\leftarrow\) induced sub-graph of \(G\) formed by the subset \(C\) of vertices;
27\((\mathbf{C}^{\prime},P^{\prime})\leftarrow\textit{CIC}(IG)\);
28 if\(|\mathbf{C}^{\prime}|>1\land\ a_{G}^{\mathbf{C}}\leq q(C)\)then
29\(\mathbf{C}\leftarrow(\mathbf{C}-C)\cup\mathbf{C}^{\prime}\);
30 update \(P\);
31
32 Return\((\mathbf{C},P)\);
33 Swap\((C,\mathbf{C},P)\)
34 forevery community \(C^{\prime}\in\mathbf{C}\) that is neighbor of \(C\)do
35 forevery pair of nodes \((i,j)\in BV(C,C^{\prime})\)do
36 swap the communities of \(i\) and \(j\) if it leads to a decrease in the quality value;
37 Return\((\mathbf{C},P)\);
```  
**Algorithm 2**Updating Communities (UC)  
**Theorem 1** (Time efficiency of the first phase of the algorithm). : _For a graph \(G=(V,E)\) with \(n\) nodes and \(m\) edges, the first phase of the algorithm, which involves the identification of \(\alpha\)-far nodes and the creation of initial communities, operates in \(O(n^{2}(n+m))\) time, where \(k\) is a constant._  
Proof. : The first phase involves constructing \(P_{\alpha}\) and creating initial communities from \(\alpha\)-far nodes. As shown in Lemma 1, \(P_{\alpha}\) can be determined in \(O(n(n+n))\) time. Hence, as the assignment of the remaining nodes to communities can take place in at most \(O(n)\) time, the construction and initialization steps require \(O(n^{2}(n+m))\) time. Having the polynomial time complexity of the first phase of the algorithm proved, one can deduce the similar complexity for the whole algorithm. Theorem 2 (Time efficiency of the whole algorithm). : _For a graph \(G=(V,E)\) with \(n\) nodes, the whole heuristic algorithm consisting of establishing initial communities and refining them operates in \(O(n^{4}(n+m))\) time._  
Proof. : Assume that the second phase iterates for \(p\) times. Then, the worst case complexity of this stage would be of \(O(3 pn^{2})\), since all the three revising operations--Merge, Split, and Swap--in this stage occur in \(O(n^{2})\). Therefore, taking the time complexity of the first phase into account, we can conclude that the whole approach functions in \(O(n^{4}(n+m))\). Theorem 3 (An approximation community detection algorithm). : _For a graph \(G=(V,E)\), the heuristic algorithm provides an approximation algorithm for community detection._  
Proof. : Note that a sufficiently small value of \(\epsilon\) makes the second phase pass through all combinations of possible partitioning, pushing it to ultimately visit the optimal set of communities \(\mathbf{C}_{\mathrm{OPT}}\) with the quality value of \(q^{*}=q_{\mathrm{G}}^{\mathrm{C}_{\mathrm{OPT}}}\). Suppose that it happens after a finite number of iterations \(l\).