Revealing the densest communities of social networks efficiently through intelligent data space reduction

The inherent structure and connectivity of a group are important features of social networks. Finding the densest subgraphs of a graph directly maps to revealing the densest communities of a social network. Various techniques, e.g., edge density, k-core, near-cliques and k-cliques, have been developed to characterize graphs and extract the densest subgraphs of the graphs. However, as extraction of subgraphs with constraints is NP-hard, these techniques face a major difficulty of processing big and/or streaming data sets from social networks. This demands new methods from the expert and intelligent systems perspective for computation of the densest subgraph problem (DSP) with big and/or streaming data. The most recent method for this purpose is the “Sampling” method. It samples the big data sets, thus reducing the data space and consequently speeding up the DSP computation. But the sampled data inevitably miss out many useful data items. A new approach is presented in this paper for accelerated DSP computation with big and/or steaming data through data space reduction without loss of useful information. It uses a sliding window of small graphs with a fixed number of edges. Then, it filters out the least connected edges for each small graph. While the small graphs are processed, subgraphs are incrementally put together to reveal the densest subgraphs. Finally, the data space previously filtered out is checked for recovery of globally important edges. The approach is incorporated with existing subgraph extraction techniques for scalable and efficient DSP computation with improved accuracy. It is demonstrated for four subgraph extraction techniques over four Twitter data sets, and is shown to outperform the “sampling” method.