Premium
Exponential quality function for community detection in complex networks
Author(s) -
Džamić Dušan,
Pei Jun,
Marić Miroslav,
Mladenović Nenad,
Pardalos Panos M.
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12538
Subject(s) - maximization , heuristic , modularity (biology) , quality (philosophy) , function (biology) , exponential function , computer science , mathematical optimization , complex network , variable neighborhood search , community structure , mathematics , algorithm , artificial intelligence , statistics , metaheuristic , mathematical analysis , philosophy , genetics , epistemology , evolutionary biology , world wide web , biology
One of the most popular topics in analyzing complex networks is the detection of its community structure. In this paper, we introduce a new criterion for community detection, called the E‐quality function. The quality of an individual community is defined as a difference between its benefit and its cost, where both are exponential functions of the number of internal edges and the number of external edges, respectively. The obtained optimization problem, maximization of the E‐quality function over all possible partitions of a network, is solved by the variable neighborhood search (VNS)‐based heuristic. Comparison of the new criterion and modularity is performed on the usual test instances from the literature. Experimental results obtained both on artificial and real networks show that the proposed E‐quality function allows detection of the communities existing in the network.