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

Authors: Trinh Anh Phuc*, Pham Dang Hai , Phan Thi Thuy Dung


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.


Dense subgraphs, greedy algorithm, randomized binary search tree, graph data structures, large scale real networks
Pages : 65-69

Related Articles:

Authors : BUI Dang Thanh*, PHAM Van Truong, NGUYEN Huy Phuong