title: Modularity-based graph partitioning using conditional expected models.
abstract: Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of the edge strength of random networks. We provide closed-form solutions for the expected strength of an edge when it is conditioned on the degrees of the two neighboring nodes, or alternatively on the degrees of all nodes comprising the network. We analytically compute the expected network under the assumptions of Gaussian and Bernoulli distributions. When the Gaussian distribution assumption is violated, we prove that our expression is the best linear unbiased estimator. Finally, we investigate the performance of our conditional expected model in partitioning simulated and real-world networks.
authors.affiliation: Department of Electrical Engineering, Signal and Image Processing Institute, University of Southern California, Los Angeles, California 90089, USA.
authors.forename: Yu-Teng
authors.initials: YT
authors.lastname: Chang
authors.forename: Richard M
authors.initials: RM
authors.lastname: Leahy
authors.forename: Dimitrios
authors.initials: D
authors.lastname: Pantazis
mesh_terms: D003196:Computer Graphics; D016014:Linear Models; D008962:Models, Theoretical; D016011:Normal Distribution