Finding Dense Components in Large-Scale Network Using Randomized Binary Search Tree ☆

Given a simple undirected graph G=(V,E), the density of a subgraph on vertex set S is defined as a ratio between the number of edges |E(S)| and the number of vertices |S|, where E(S) is the set of edges induced by vertices in S. Finding the maximum density subgraph have become an intense study in recent years, especially in social network era. Being based on a greedy algorithm connects with a suitable graph data structure, we have reduced its time complexity by using randomized binary search tree, also called treap. We make the complexity analysis in both time and memory requirements, including computational experiments in large scale real networks.