2020/12/17 by Omid Madani, Thanh Ngo, Madani, Omid +13
Computer Science · Mathematics · Physics and Astronomy · Psychology · #Artificial Intelligence (cs.AI) #Artificial intelligence #Binomial (polynomial) #Complex Network Analysis Techniques #Computer science #Data mining #FOS: Computer and information sciences #Graph #Machine Learning (cs.LG) #Machine learning #Mathematics #Mental Health Research Topics #Opinion Dynamics and Social Influence #Ranking (information retrieval) #Salient #Social and Information Networks (cs.SI) #Statistics #Theoretical computer science #cs.AI #cs.LG #cs.SI
paper · pdf · doi:10.48550/arxiv.2012.09968
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/12/17 · openalex publication_date 2020/12/17 · arxiv updated 2020/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An important task of community discovery in networks is assessing significance of the results and robust ranking of the generated candidate groups. Often in practice, numerous candidate communities are discovered, and focusing the analyst's time on the most salient and promising findings is crucial. We develop simple efficient group scoring functions derived from tail probabilities using binomial models. Experiments on synthetic and numerous real-world data provides evidence that binomial scoring leads to a more robust ranking than other inexpensive scoring functions, such as conductance. Furthermore, we obtain confidence values (p-values) that can be used for filtering and labeling the discovered groups. Our analyses shed light on various properties of the approach. The binomial tail is simple and versatile, and we describe two other applications for community analysis: degree of community membership (which in turn yields group-scoring functions), and the discovery of significant edges in the community-induced graph.