# Large-Scale Complex Network Community Detection Combined with Local Search and Genetic Algorithm
## 3 Proposed Method
### Complex Network Community Detection Concept
The specific formula is as follows:  
\[\begin{array}{ll}NMI  
of known actual communities. The larger the _NMI_ value, the better the community partitioning effect obtained by the community detection algorithm. When the _NMI_ value is \(1\), it indicates that the discovered community is completely consistent with the real community.  
1. Community detection algorithm
2. GN algorithm  
The GN algorithm is a cohesive community structure discovery algorithm. Based on the characteristics of high cohesion within communities and low cohesion among communities, the algorithm gradually removes the edges between communities to obtain a relatively cohesive community structure. The algorithm uses the concept of edge median to detect the position of an edge. The edge median of an edge is defined as the number of times the shortest path between all vertices on the network passes through the edge. The basic idea is to realize the division of the network by continuously deleting the edge with the largest number of edges in the network until all the edges in the network are deleted. It is based on the internal links of the community, and the shortest path through them is relatively small; while the links between the communities have relatively shortest paths. The flow of the GN algorithm is as follows:  
1. Calculate the edge number of each edge in the network.
2. Delete the edge with the largest median.
3. Recalculate the number of edges of the remaining edges in the network.
4. Repeat steps (b) and (c) until the nodes in the network are divided into separate communities.  
2. Fastgreedy algorithm  
The GN algorithm is only suitable for small networks because it needs to repeatedly calculate the edge number of the edge and has a large time overhead. Compared to the Internet, e-mail networks and other large networks with hundreds of millions of nodes, it is clear that the GN algorithm cannot meet the requirements. Based on this, the Fastgreedy algorithm is a fast search algorithm developed on the basis of the GN algorithm [20; 21]. In fact, the essence of the algorithm is one of the cohesive algorithms based on greedy thought. The steps of the Fastgreedy algorithm are as follows:  
1. Initialize the network into n communities and consider each node as an independent community.
2. Calculate the module \(Q\) value corresponding to the combination of the two communities, and increase or decrease the maximum or the maximum along the module increment \(\Delta Q\) community consolidation in a small direction: \[\Delta Q=e_{ij}+e_{ji}-2a_{i}a_{j}=2(e_{ij}-a_{i}a_{j})\] (7)
3. Repeat (b) until all the communities in the network are merged into one large community, the algorithm stops, and the community partition result corresponding to the maximum module degree in the merge process is found. 4. LFM algorithm  
The LFM algorithm is different from the community discovery algorithm that understands the community structure from a global perspective. The basic premise of the algorithm is that the community structure is a local structure, that is, the community relationship to which the node belongs is most related to its neighbor nodes. This idea is consistent with the current situation of many large-scale networks. For example, in social networks, individual community relationships do not need to determine their community affiliation based on understanding the entire human relationship network. The LFM algorithm defines a fitness function:\[f_{G}=\frac{k_{in}^{G}}{\left(k_{in}^{G}+k_{out}^{G}\right)^{\partial}} \tag{8}\]  
where \(k_{in}^{G}\) and \(k_{out}^{G}\) represent the degree in the community \(G\) (the sum of the weights of the edges in the community \(G\)) and the degrees outside the community (the sum of the weights between the \(G\) and other communities), and \(\partial\) is a positive resolution parameter. Used to control the size of the community, so the LFM algorithm is also a community discovery algorithm that can detect hierarchical community structures.