Community structure extraction in directed network using triads

Abstract

Community detection in directed networks appears as one of the most relevant topics in the field of network analysis. One of the common themes in its formalizations is information flow clustering in a network. Such clusters can be extracted by using triads, expected to play an important role in the detection of that type of communities since communities could be centered round core nodes called kernels. Triads in directed graphs are directed sub-graphs of three nodes involving at least two links between them. To identify communities in directed networks, this paper proposes an in-seed-centric scheme based on directed triads. We also propose a new metric of the communities' quality based on the triad density of communities. To validate our approach, an experiment was conducted on some networks showing it has better performance on triad-based density over some state-of-the-art methods.

Keywords:

• Networks analysis
• directed networks
• kernel
• community detection
• triad

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 http://www.aaai.org/ocs/index.php/ICWSM/09/paper/view/154

2 https://www.R-project.org

3 http://www.cs.umd.edu/projects/linqs/projects/lbc/

Additional information

Notes on contributors

Félicité Gamgne Domgue

Félicité Gamgne Domgue is a PhD student at the Department of Computer Science of the University of Yaounde I. In her research she studies social network analysis and graph mining in order to detect communities.

Norbert Tsopze

Norbert Tsopze is a senior lecturer at the Department of Computer Science of the University of Yaounde I and member of the local UMMISCO research team. His research interests include datamining, formal concept analysis, neural network, deep learning, text analysis, social network analysis, classification. He is also director of many Master and PhD students.

René Ndoundam

Réné Ndoundam is an Associate Professor of Computer Science at Department of Computer Science of University of Yaoundé 1. His interest area of research includes: Automata, Complexity, Steganography and Recommandation systems, graph theory.