Algorithms for network modularity maximization

Daniel Aloise (1) , Sonia Cafieri (2) , Gilles Caporossi (1) , Pierre Hansen (1, 3) , Leo Liberti (3) , Sylvain Perron (1)

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

Networks are often used to represent complex systems arising in a variety of fields. Social networks model interactions among people. Telecommunication networks model communications betwen them, such as in the WorldWide Web. Transportation networks model movements of goods and passengers. Biological networks model interactions between organisms, such as in food networks. A network (or graph) G = (V,E) is composed of a set of vertices, representing the entities of the system under study, and a set of edges joining pairs of vertices and representing a relation holding for such pairs. Identifying communities, or clusters, in complex networks is a topic of particular interest and is currently a very active research domain.

Mots clés: clustering; network; graph; community; modularity; row and column generation

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

Daniel Aloise, Sonia Cafieri, Gilles Caporossi, Pierre Hansen, Leo Liberti, et al.. Algorithms for network modularity maximization. ROADEF 2010, 11ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2010, Toulouse, France. ⟨hal-00934772⟩