IEEE Transactions on Knowledge and Data Engineering · 2011 · 96 citations · 43 references
Life SciencesBioinformaticsComputational BiologyData MiningProtein-protein InteractionsBiological NetworksGraph TheoryProtein-protein Interaction AnalysisProtein-protein Interaction NetworksSocial Network AnalysisClusteringCorrelationCorrelation ClusteringProbabilistic Approximation AlgorithmsProbabilistic ClusteringProtein Interaction Network ClusteringProtein-protein Interaction Network AnalysisStatistical Significance Testing
We study the problem of clustering probabilistic graphs. Similar to the problem of clustering standard graphs, probabilistic graph clustering has numerous applications, such as finding complexes in probabilistic protein-protein interaction (PPI) networks and discovering groups of users in affiliation networks. We extend the edit-distance-based definition of graph clustering to probabilistic graphs. We establish a connection between our objective function and correlation clustering to propose practical approximation algorithms for our problem. A benefit of our approach is that our objective function is parameter-free. Therefore, the number of clusters is part of the output. We also develop methods for testing the statistical significance of the output clustering and study the case of noisy clusterings. Using a real protein-protein interaction network and ground-truth data, we show that our methods discover the correct number of clusters and identify established protein relationships. Finally, we show the practicality of our techniques using a large social network of Yahoo! users consisting of one billion edges.
43
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Global landscape of protein complexes in the yeast Saccharomyces cerevisiae
Nevan J. Krogan, Gerard Cagney, Haiyuan Yu et al. · Nature · 2006 · 3K citations
The Complexity of Enumeration and Reliability Problems
Leslie G. Valiant · SIAM Journal on Computing · 1979 · 2.1K citations
Satu Elisa Schaeffer · Computer Science Review · 2007 · 1.6K citations