Locating leading components in networks through the optimization of nonlinear modularity functions

In this thesis we analyze the problem of bi-partitioning a given graph. We start from a natural linear view of the problem and then we move to a non linear extension that gives us a strict relation between the best bi-artitiong and the maximum of a continuous functions. Moreover we prove a new constrained formulation of the maximization problem with a convex and compact region as feasible set. From there we decide to approximate the objective function with a C1 function in order to use first-order local optimization algorithms. We show these algorithms, giving for each of them convergence theorems and related schemes. Finally we describe a probabilistic global method that we apply first on a toy model graph, given by a stochastic block model, and then on real world graphs. We compare results with some state of the art methods, trying to highlight what is the strength of our approach and which is the best algorithm to use.