PC Seminar: Fast and Accurate Algorithms to Calculate Expected Modularity in Probabilistic Networks

Abstract: Many real-life networks are uncertain and can thus be better modeled using probabilistic networks, where each edge is associated with a probability representing the likelihood of its existence. Probabilistic networks have been studied in many applications, such as protein-protein interaction networks, social networks, and co-authorship networks. 

Modularity is a fundamental measure to study networks, for example, to study communities and core-periphery structures. However, while the problem of finding modules in probabilistic networks has received some attention in the literature, no existing work has studied how to extend modularity to this context. Particularly, it is challenging to efficiently calculate expected modularity when all possible worlds are considered. To address this problem, we propose two algorithms, namely PWP^EMOD and APWP^EMOD, partitioning the possible worlds based on their modularities to significantly reduce the number of probability calculations.

This is a seminar in our seminar series on Probability and Combinatorics (PC).