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, 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. Evolutionary algorithms are generally able to find good solutions in reasonable amounts of time, but the computation time increases with the problem size and complexity. Parallel programming paradigm is a promising choice that attempts to make Evolutionary algorithms faster. Also, social networks are normally characterized with large number of nodes making their analysis naturally amenable to parallel computing. In recent years, programmable Graphics Processing Units (GPUs) have evolved into massively parallel environments with tremendous computational power. NVIDIA Compute Unified Device Architecture (CUDA) technology, one of the leading general-purpose parallel computing architectures with hundreds of cores that can concurrently run thousands of computing threads is used to implement the algorithm. This paper presents a GPU-based parallel implementation of a variant of quantum inspired genetic algorithm for the problem of community structure detection in social networks.

Featured Image

Photo by NASA on Unsplash

Photo by NASA 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