Community Structure Detection for Directed Networks Through Modularity Optimisation

Lingjian Yang; Jonathan C. Silva; Lazaros G. Papageorgiou; Sophia Tsoka

doi:10.3390/a9040073

Community Structure Detection for Directed Networks Through Modularity Optimisation

Lingjian Yang
, Jonathan C. Silva
, Lazaros G. Papageorgiou^*
, Sophia Tsoka

^*Corresponding author for this work

Informatics

UCL University College London
Department of Informatics

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

267 Downloads (Pure)

Abstract

Networks constitute powerful means of representing various types of complex systems, where nodes denote the system entities and edges express the interactions between the entities. An important topological property in complex networks is community structure, where the density of edges within subgraphs is much higher than across different subgraphs. Each of these subgraphs forms a community (or module). In literature, a metric called modularity is defined that measures the quality of a partition of nodes into different mutually exclusive communities. One means of deriving community structure is modularity maximisation. In this paper, a novel mathematical programming-based model, DiMod, is proposed that tackles the problem of maximising modularity for directed networks.

Original language	English
Article number	73
Number of pages	10
Journal	Algorithms
Volume	9
Issue number	4
DOIs	https://doi.org/10.3390/a9040073
Publication status	Published - 1 Nov 2016

Keywords

Community detection
Complex networks
Directed networks
Integer programming
Modularity optimisation

Access to Document

10.3390/a9040073Licence: CC BY

Community Structure Detection_YANG_Accepted18Oct2016_GOLD VoRFinal published version, 259 KBLicence: CC BY

Cite this

@article{7ff2b1e265f24491aa86c30563e567a4,

title = "Community Structure Detection for Directed Networks Through Modularity Optimisation",

abstract = "Networks constitute powerful means of representing various types of complex systems, where nodes denote the system entities and edges express the interactions between the entities. An important topological property in complex networks is community structure, where the density of edges within subgraphs is much higher than across different subgraphs. Each of these subgraphs forms a community (or module). In literature, a metric called modularity is defined that measures the quality of a partition of nodes into different mutually exclusive communities. One means of deriving community structure is modularity maximisation. In this paper, a novel mathematical programming-based model, DiMod, is proposed that tackles the problem of maximising modularity for directed networks.",

keywords = "Community detection, Complex networks, Directed networks, Integer programming, Modularity optimisation",

author = "Lingjian Yang and Silva, \{Jonathan C.\} and Papageorgiou, \{Lazaros G.\} and Sophia Tsoka",

year = "2016",

month = nov,

day = "1",

doi = "10.3390/a9040073",

language = "English",

volume = "9",

journal = "Algorithms",

issn = "1999-4893",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "4",

}

TY - JOUR

T1 - Community Structure Detection for Directed Networks Through Modularity Optimisation

AU - Yang, Lingjian

AU - Silva, Jonathan C.

AU - Papageorgiou, Lazaros G.

AU - Tsoka, Sophia

PY - 2016/11/1

Y1 - 2016/11/1

N2 - Networks constitute powerful means of representing various types of complex systems, where nodes denote the system entities and edges express the interactions between the entities. An important topological property in complex networks is community structure, where the density of edges within subgraphs is much higher than across different subgraphs. Each of these subgraphs forms a community (or module). In literature, a metric called modularity is defined that measures the quality of a partition of nodes into different mutually exclusive communities. One means of deriving community structure is modularity maximisation. In this paper, a novel mathematical programming-based model, DiMod, is proposed that tackles the problem of maximising modularity for directed networks.

AB - Networks constitute powerful means of representing various types of complex systems, where nodes denote the system entities and edges express the interactions between the entities. An important topological property in complex networks is community structure, where the density of edges within subgraphs is much higher than across different subgraphs. Each of these subgraphs forms a community (or module). In literature, a metric called modularity is defined that measures the quality of a partition of nodes into different mutually exclusive communities. One means of deriving community structure is modularity maximisation. In this paper, a novel mathematical programming-based model, DiMod, is proposed that tackles the problem of maximising modularity for directed networks.

KW - Community detection

KW - Complex networks

KW - Directed networks

KW - Integer programming

KW - Modularity optimisation

UR - https://www.scopus.com/pages/publications/84999622462

U2 - 10.3390/a9040073

DO - 10.3390/a9040073

M3 - Article

AN - SCOPUS:84999622462

SN - 1999-4893

VL - 9

JO - Algorithms

JF - Algorithms

IS - 4

M1 - 73

ER -

Community Structure Detection for Directed Networks Through Modularity Optimisation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Community structure detection in complex networks

MAARS: Microbes in Allergy and Autoimmunity Related to Skin

Cite this

Community Structure Detection for Directed Networks Through Modularity Optimisation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Community structure detection in complex networks

MAARS: Microbes in Allergy and Autoimmunity Related to Skin

Cite this