Quantum inspired algorithm for community detection in social networks

What is it about?

A social network is a system of interconnected entities in a domain and is used to represent relationships between these entities. For example, a network of communication between dolphins, transportation networks, economic networks, online social networks. Social networks may exhibit hierarchy in the network structure, the sub-networks being popularly termed as communities. The communities become interesting when the entities within a community are more interrelated to each other than to those in a different community. Detection of communities allows better understanding and visualization of networks and also brings out many interesting features that may be missed if we look at the network as a whole. Evolutionary algorithms (EA) are efficient search and optimization method based on the principles of natural biological evolution. A quantum-inspired genetic algorithm (QIGA) is an evolutionary algorithm using the quantum computing concepts for individual representation and variation operators to generate candidate solutions followed by the use of a classical algorithm to evaluate these candidate solutions. A quantum-inspired genetic algorithm works with quantum population comprising of chromosomes. Each chromosome is represented as a string of qubits with the advantage that it can represent a linear superposition of states in search space probabilistically. Superposition enables a quantum chromosome to store exponentially more data than a classical chromosome of the same size. Additionally, a qubit-based formulation has a better characteristic of population diversity than classical representation. This paper presents a variant of quantum inspired genetic algorithm for the problem of community structure detection in social networks.

Featured Image

Photo by Clint Adair on Unsplash

Photo by Clint Adair on Unsplash

Why is it important?

Narayanan and Moore (1996) stressed on the need of computational paradigms like the quantum-inspired algorithms that can benefit from their proximity to the quantum concepts and will therefore require less translation to quantum machine language as and when the quantum computers become available than their classical counterparts.

Perspectives