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.

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

Brotto, Fabio
2017/2018

Abstract

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.
2017-09-22
59
File in questo prodotto:
File Dimensione Formato  
tesi_Brotto.pdf

accesso aperto

Dimensione 7.91 MB
Formato Adobe PDF
7.91 MB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/28184