March 28, 2011 to April 20, 2011
Europe/Stockholm timezone

Detecting community structures in uncertain networks using ensemble clustering

Mar 31, 2011, 9:00 AM


Mr Johan Dahlin (Swedish Defense Research Agency)


During recent years many different methods to detect community structures in complex networks have been developed. Despite significant efforts from many different scientists from different fields, no completely satisfactory method to detect communities has been developed. In this talk, we present a method to merge the results from several different community detections run into a single final estimated community structure. Each run can either use a different method or else an ensemble of results from the same algorithm an be merged. We propose three different methods for the merge. Two of these are related to ensemble clustering methods used in standard data clustering problems. We apply these three methods on some different problems to demonstrate their usefulness. Some existing methods are stochastic in nature and generate different results for each run. Using the merging methods, one can use the collective information from the entire ensemble of possible community structures to find the most likely structure. This is shown to improve the performance of some stochastic algorithms. Another problem is related to the problem of uncertain Social Networks. In these networks, edges are not known with certainty to exist. Instead, a probability (or probability interval) is given for their existence. Using methods from statistical simulation, one can create an ensemble of networks that are consistent with the uncertain network. Applying existing methods for detecting community structures on each network from the ensemble creates a large number of different candidate community structures (one for each realization of the uncertain network). Applying the merging methods presented in this talk, one can merge (fuse) these different candidate structures into one, thus finding the community structure of the uncertain network.

Presentation materials

There are no materials yet.