Multiple interaction strategies, parameter estimation, and clustering in networks (PhD home defence)

2016. 09. 29. 16:15
Ahmed ElBanna

The thesis consists of three strongly intertwining chapters. Each of them uses spectral clustering tools or mixture models to assign scores or estimate parameters corresponding to the vertices of large unweighted or weighted graphs.

In the first Chapter, we investigate interaction strategies in networks. Our objective is to maximize the payoff of the agents simultaneously. In the classical strategic complements or substitutes setup, the objective function has a linear and a quadratic part, and maximized under linear constraints by using classical tools of operations research. We use quadratic objective functions on linear or quadratic constraints, and will show how existing results of combinatorial graph theory and spectral clustering can be used to solve the optimization problems, where solutions are closely related to maximal cliques, dominant sets, or spectral clusters. Together with clustering, we also use evaluation of the vertices and edges, which give optima of potential functions.

In the second Chapter, we introduce a semiparametric block model for graphs, where the within- and between-cluster edge probabilities are not constants within the blocks, but are described by logistic type models, reminiscent of the 50 years old Rasch model and the newly introduced α–β models. Our purpose is to give a partition of the vertices of an observed graph so that the induced subgraphs and bipartite graphs obey these models, where their strongly interlaced parameters give multiscale evaluation of the vertices at the same time. In this way, a profoundly heterogeneous version of the stochastic block model is built via mixtures of the above submodels, while the parameters are estimated with a special EM iteration.

In the third Chapter we will discuss how graph based matrices are capable to find classification of the graph vertices with small within- and between-cluster discrepancies. The structural eigenvalues together with the corresponding spectral subspaces of the normalized modularity matrix are used to find a blockstructure in the graph. We also investigate relations between spectral properties, multiway discrepancies, and degree distribution of generalized random and quasirandom graphs.

We use advanced linear algebra, probability, and theory of the exponential distributions. Simulation results and real-life examples are also presented.