Binomial Tails for Community Analysis

Automated discovery of candidate communities in networks finds a variety of applications in physical and social sciences (biological and biochemical networks, physical and virtual human networks) [1, 2]. Given a graph representing binary relations among nodes, informally and intuitively, a community corresponds to a subgraph, i.e. a subset of nodes, with relatively high edge density among the community members (nodes of the subgraph), and comparatively lower density of edges going outside the community. Defining communities more precisely and what overall community structure may be in various domains, and design of efficient robust algorithms for uncovering such in networks has been the subject of much research [1, 3]. In our use-case, we are interested in the automated discovery and effective presentation of candidate communities comprised of computers (hosts) in an enterprise network. In particular this effort is a component of a tool that provides a user, such as a security administrator of an organization, visibility into their complex network, and importantly helps the user partition the network into groups corresponding to geographic partitions, different departments, and hosts running different applications in the organization. This partitioning and naming of the groups is a necessary step in defining and maintaining network security policies, aka network segmentation: hosts in different groups (segments) can only communicate on a few well-defined and restricted channels. Such policy enforcement severely limits penetration and spread of malware and hackers. This step of grouping hosts and assigning meaningful names/labels to the groups, with the human in the loop, is also highly useful in generating insights, for example in uncovering broad patterns of communications with applications not just for security but also for network optimization.