Expected Nodes: A Quality Function for the Detection of Link Communities

Noé Gaumont 1, * François Queyroi 1 Clémence Magnien 1 Matthieu Latapy 1
* Corresponding author
1 ComplexNetworks
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : Many studies use community detection algorithms in order to understand complex networks. Most papers study node communities, i.e. groups of nodes, which may or may not overlap. A widely used measure to evaluate the quality of a community structure is the modularity. However, sometimes it is also relevant to study link partitions rather than node partitions. In order to evaluate a link partition, we propose a new quality function: Expected Nodes. Our function is based on the same inspiration as the modularity and compares, for a given link group, the number of incident nodes to the expected one. In this short note, we discuss the advantages and drawbacks of our quality function compared to other ones on synthetics graphs. We show that Expected Nodes is able to pass some fundamental sanity criteria and is the one that best identifies the most relevant partition in a more realistic context.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

Contributor : Noé Gaumont <>
Submitted on : Thursday, September 10, 2015 - 2:11:37 PM
Last modification on : Thursday, March 21, 2019 - 1:13:08 PM
Long-term archiving on : Monday, December 28, 2015 - 11:55:03 PM


Files produced by the author(s)





Noé Gaumont, François Queyroi, Clémence Magnien, Matthieu Latapy. Expected Nodes: A Quality Function for the Detection of Link Communities. 6th Workshop on Complex Networks CompleNet 2015, Mar 2015, New-York, United States. pp.57-64, ⟨10.1007/978-3-319-16112-9_6⟩. ⟨hal-01196796⟩



Record views


Files downloads