Exponential quality function for community detection in complex networks

• Published date: 01 January 2020
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12538

Intl. Trans. in Op. Res. 27 (2020) 245–266

DOI: 10.1111/itor.12538

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Exponential quality function for community detection

in complex networks

Duˇ

san Dˇ

zami´

ca,c,JunPei

b, Miroslav Mari ´

cc, Nenad Mladenovi´

cdand

Panos M. Pardalose

aFaculty of Organizational Sciences, University of Belgrade, JoveIli ´

ca 154, 11000 Belgrade, Serbia

bSchool of Management, Hefei University of Technology,Tunxi Road 193, 230009 Hefei City, People’s Republic of China

cFaculty of Mathematics, University of Belgrade, Studentskitrg 16, 11000 Belgrade, Serbia

dMathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Belgrade, Serbia

eFaculty of Engineering, University of Florida, 401 Weil Hall, Gainesville, FL 32611, USA

E-mail: dzamic@fon.bg.ac.rs [D ˇ

zami´

c]; feiyijun198612@126.com [Pei];maricm@matf.bg.ac.rs [Mari´

c];

nenad@mi.sanu.ac.rs [Mladenovi´

c]; pardalos@ufl.edu [Pardalos]

Received 26 February2017; received in revised form 21 February 2018; accepted 23 February 2018

Abstract

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.

Keywords:complex network; community detection; quality function; exponential ratio; variable neighborhood search

1. Introduction

Many types of complex systems in the real world can be modeled as networks or graphs where the

vertices represent the components, and the edges their interactions. Therefore, studying complex

systems as the corresponding networks enables many useful applications of graph theory and

network science. A large number of networks have substantial nontrivial topological features, i.e.,

patterns of connection between their elements are neither purely regular nor purely random. One

common feature is the community structure, presented as the network divided into groups that

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

246 D. Dˇ

zami´

c et al. / Intl. Trans. in Op.Res. 27 (2020) 245–266

have great density of internal connections and low density of external connections. For example,

communities in a citation network might represent related papers on a single topic; communities on

the world wide web might represent pages of related topics; metabolic networks have communities

that are based on functional groupings, etc. As it is possible to detect them, they can help us to

visualize, understand, and exploit a networkmore effectively (for more details,see Girvan and Watts

and Strogatz, 1998; Newman, 2002; and Thai and Pardalos, 2011).

1.1. Applications

Community detection has concrete applications in very diverse research areas. Pinheiro (2012) used

community detection in a network formed on voice calls, and text messages, between users to

understand behavior and occurrence of the fraud events in telecommunication networks. Also, it

can be used in code refactoring, i.e,. the process of changing a software system in such a way that it

does not alter the external behavior of the code and improves its internal structure. Pan et al. (2013)

presented an approach where refactoring software packages were performed through community

detection in the network that represents classes and their dependencies. Community detection in a

customer network on e-commerce web sites enables us to set up an efficient recommendation system

that better guides customers through retailers list of items. Zanin et al. (2008) presented the methods

for systems that recommend the most suitable products to customers by predicting their interests.

The community structure may indeed provide useful information and insights for link prediction

(L¨

u and Zhou, 2011). Identifying cohesive subgroups in social networks(Xanthopoulos et al., 2009)

proves to be useful in predicting the patterns of interactions that help in studying social processes

and beliefs within a subgroup or a community. Chen et al. (2012) explored the effect of overlapping

community structure on the susceptible-infected-susceptible (SIS epidemic model, used to study

disease spread mechanisms, to predict future course of the outbreak, and to evaluate strategies to

control epidemic. Ren and Wang (2014) presented a simple network model with the time-varying

community structure and investigated SIS epidemic-spreading processes.

1.2. Litera ture revie w

There is no precise definition of community notion, but there are many ways to formalize it. One

way could be specifying some rules that vertices in a community must respect, i.e. Radicchi et al.

(2004) defined community in its strong and weak sense. In the strong sense, each vertex has more

connections within the community than with the rest of the network. In the weak sense, the sum of

all degrees within a community is larger than the sum of all degrees toward the rest of the network.

Often, communities are algorithmically defined (Lai et al., 2011; Wang and Li, 2013; Eustace et al.,

2015), i.e., they are just the final product of the algorithm, without any precise a priori definition.

Another way to define and identify community is to specify an objective function to maximize or

minimize. Hence, variousobjective functions have been proposed, such as minimum sum of squares

(Carrizosa et al., 2011), ratio cut objective (Alpert and Yao, 1995), edge ratio objective (Cafieri et al.,

2010), and normalized cut (Shi and Malik, 2000). The most used one appears to be modularity,

first proposed by Newman and Girvan (2004). Modularity measures the quality of a partition of a

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies