Fuzzy Cognetive Maps to improve the Genetic Algorithm for community detection
Explanation of the Paper Fuzzy Cognitive Map-Based Genetic Algorithm for Community Detection.
Introduction
- Detecting communities is an active area of research.
- Detecting communities in networks can be done using the genetic Algorithm(GA).
- Many approaches are trying to improve the performance of GA in detecting communities.
- Fuzzy cognetive maps are applied in this paper to reduce convergence time.
History of the Field
Community Detection:
In this section our interest is community detection. So let’s dive in.
A community is a group of densly connected nodes in a network. Nodes of the same community share similar properties.
Community detection helps in understanding individual units better. Moreover, It can help in studying problems of specefic communities (ex: “Diabetes” and “Obesity”).
Fuzzy Cognetive Maps (FCM):
An FCM is a weighted directed graph where Nodes represent concepts and Edges represent Relationships between concepts. Edges can also be refered to as weights. They can be Positive or negative in an FCM.
- W_ij > 0 : the concepts C_i and C_j are related.
- W_ij =< 0 : the concepts C_i and C_j are not related.
The Genetic Algorithm (GA):
GAs are Based on Darwin’s theory “Survival of the fittest”. a Genetic Algorithm is a set of optimization techniques inspired by the biological evolution process that can be used to detect communities in a given network.
In a Genetic Algorithm :
1- we choose a random number of communiti es that we want to detect and affect the nodes of the network randomly across these communities.
2- Now an evaluation of the fitness of the clustering (community detection) is performed. Different metrics are available but the most used one is modularity.
3- Ranking of chromosomes (Clustering configuration) is done with each iteration. That assures that best clustering configuration is on the top of the list and has maximum modularity.
4- The genetic algorithm allows a set of genetic operations between chromosomes. (Crossover & Mutation)
5- The genetic Algorithm is iterative. It loops until the terminating condition is met.
6-Once the finishing condition is met, The chromosome (clustering configuration) with highest modularity is returned as Results.
Proposed Approach in the Paper:
In the paper Fuzzy Cognitive M aps (FCM) are used to determine the number of Communities before running the Genetic Algorithm.
=> No more Random initialization of clusters number, Instead it is set to the value of Focal nodes determined by FCM
Example + Steps:
1 — Calculate an initial state vector:
For each node “v” in the network calculate the betweeness centralarity g(v).
σ_st(v): The total number of shortest paths from the node “s” to the node “t” and that passes by the node “v”.
σ_st: The total number of shortest paths from the node “s” to the node “t”.
2 — Iterate until convergence:
keep multiplying the initial state vector ‘A’ by the weight matrix ‘W’ until convergence.
3 — Determine the focal nodes:
Once we have the final vector state we calculate its mean value. Then We count the number of values in the final vector state that are >= than the mean value calculated. This is the number of focal nodes determined.
For example if we have this state vector. and caluclate its mean value we’ll get an apporximate value of 0.77. Now we check the number of elements in the vector that are greater or equal than 0.77 and we’ll get 5 as a result.
=> 5 focal nodes are determined.
Once the number of focal nodes is determined, the genetic algorithm is initialized by attributing nodes randomly to communitites in the range of the determined number of focal nodes.
Experimental Results:
Experimentation was done on an intel I7 system with 32GB of RAM and NVIDIA GeForce GTX 1050 GPU.
8 different Benchmark Dataset were tested. and are shown in the next figure.
Computational complexity was computed for GA community detection and FCM-based GA community detection.
Emperical results states that incorporating fuzzy cognitive maps in genetic algorithms for community detection reduces significantly convergence time.
Conclusion:
A genetic algorithm-based approach with the use of the FCM tool was presented in this paper. The initial number of communities calculated by the FCM improved significantly the overall computational time of the algorithm.
