2015/10/16 by Cheng‐Shang Chang, Cheng-Shang Chang, Chang, Cheng-Shang +9
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Bioinformatics and Genomic Networks #Bivariate analysis #Centrality #Combinatorics #Complex Network Analysis Techniques #Computer science #FOS: Computer and information sciences #FOS: Physical sciences #Graph #Hierarchy #Joint probability distribution #Marginal distribution #Mathematics #Modularity (biology) #Opinion Dynamics and Social Influence #Partition (number theory) #Physics and Society (physics.soc-ph) #Probabilistic logic #Social and Information Networks (cs.SI) #Statistics #Theoretical computer science #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1510.04828
published in arXiv (Cornell University) (Cornell University)
arxiv created 2015/10/16 · openalex publication_date 2015/10/16 · arxiv updated 2015/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In our recent works, we developed a probabilistic framework for structural analysis in undirected networks. The key idea of that framework is to sample a network by a symmetric bivariate distribution and then use that bivariate distribution to formerly define various notions, including centrality, relative centrality, community, and modularity. The main objective of this paper is to extend the probabilistic framework to directed networks, where the sampling bivariate distributions could be asymmetric. Our main finding is that we can relax the assumption from symmetric bivariate distributions to bivariate distributions that have the same marginal distributions. By using such a weaker assumption, we show that various notions for structural analysis in directed networks can also be defined in the same manner as before. However, since the bivariate distribution could be asymmetric, the community detection algorithms proposed in our previous work cannot be directly applied. For this, we show that one can construct another sampled graph with a symmetric bivariate distribution so that for any partition of the network, the modularity index remains the same as that of the original sampled graph. Based on this, we propose a hierarchical agglomerative algorithm that returns a partition of communities when the algorithm converges.