# Large-Scale Complex Network Community Detection Combined with Local Search and Genetic Algorithm
## 3 Proposed Method  
### Complex Network Community Detection Concept  
(1) Community structure of complex networks  
In addition to the characteristics of preference connection, small world effect, power law distribution and scale-free topology, complex networks also exhibit community structure characteristics. In order to better study and analyze the community structure of the network, the community is further divided into two types: strong community and weak community. For a community \(C=\{v1,v2\dots\)\(vc\}\), any node in the community satisfies:  
\[k_{i}^{in}>k_{i}^{out}\quad\forall vi\in C \tag{1}\]  
where \(k_{i}^{in}\) is the number of connections between the node \(vi\) and the internal nodes of the community and \(k_{i}^{out}\) is the number of connections between the node \(vi\) and the external nodes of the community, apparently \(k_{i}=k_{i}^{in}+k_{i}^{out}\). In this way, community \(C\) is called a strong community. If the community meets:\[\sum_{i}^{c}k_{i}^{in}>\sum_{i}^{c}k_{i}^{out}\quad\forall i\in C\] (2) Then community \(C\) is called a weak community. 2. Community structure quality evaluation indicators
3. Modular  
The network module degree is defined as follows: the difference between the number of connected edges in the network module and the number of connected edges in the random case refers to the proportion of the number of connected sides of the entire network. Assume that for Network \(C\), if it has a clear modular structure, the network is a random network of the same situation. Then, the sum of the number of internal sides of each module in the network \(C\) must be greater than the sum of the number of connected sides in each community in the network. Based on the above assumptions, the following expression can be defined:  
\[ \begin{array}{ll}Q&=\frac{1}{2m}\sum\limits_{vu}\left[A_{vw}-\frac{k_{v}k_ {w}}{2m}\right]\delta(c_{v},c_{v})\\ &=\sum\limits_{i}\left(e_{ii}-a_{i}^{2}\right)\\ \\ e_{ii}&=\frac{1}{2m}\sum\limits_{vw}A_{vw}\delta(c_{v},i)\delta(c_{uv},i)\\ \\ a_{i}&=\frac{1}{2m}\sum\limits_{v}k_{v}\delta(c_{v},i)\end{array}  \tag{3}\]  
where \(A\) represents the adjacency matrix of network \(C\). If there is an edge between node \(v\) and node \(w\), then \(A_{v,w}=1\), otherwise \(0\). \(m\) represents the total number of connected sides of the network, and \(2m\) represents the total number of degrees of the network. \(k_{v}\), \(k_{w}\) represent the degrees of nodes \(v\), \(w\), respectively. \(e_{ii}\) represents the ratio of all edges in community \(i\) to all sides of the entire network. \(a_{i}\) represents the number of connections for the \(i\)-th community and all other nodes within the community. The \(\delta\) function indicates that when the nodes \(v\), \(w\) belong to the same community, it is \(1\), otherwise it is \(0\), which ensures that only the connected edges in the community are considered. 3. NMI  
Mutual information is a measure of the correlation between random variables in probability theory and information theory and is usually used to measure the degree of dependence between each other. It is introduced into the community structure quality evaluation and normalized, which is normalization mutual information [19]. In the actual calculation, a corresponding hybrid matrix \(N\) is generated according to the community division of the network and the community partition obtained by the community detection algorithm, wherein the element \(N_{ij}\) in the matrix \(N\) represents the shared node between the actual community \(C_{i}\) and the community \(C_{j}\) obtained by the algorithm.