Hierarchical clustering for the identification of communities in networks

Sonia Cafieri (1) , Pierre Hansen (2, 3) , Leo Liberti (3)

1 ENAC - Ecole Nationale de l'Aviation Civile
2 HEC Montréal - HEC Montréal
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

The analysis of networks and in particular the identification of communities, or clusters, is a topic of active research and attracts an increasing attention in the operations research as well as the physics communities. Complex systems arising in a variety of fields can be represented as networks, or graphs, where the set of vertices is given by the entities under study and the edges represent relations holding for pairs of vertices. A typical example is given by social networks, modeling interactions among people. Other real-life applications include communicatons networks, such as theWorldWide Web, and transportation networks, representing movements of people or goods.

Mots clés: clustering; network; graph; community; modularity; hierarchical heuristic

Domaines: Mathématiques [math]; Optimisation et contrôle [math.OC]

Sonia Cafieri, Pierre Hansen, Leo Liberti. Hierarchical clustering for the identification of communities in networks. ROADEF 2011, 12ème congrès annuel de la Société française de Recherche Opérationnelle et d'Aide à la Décision, Mar 2011, St-Etienne, France. ⟨hal-00934763⟩