中央研究院 資訊科學研究所

Networks are a general language for describing social, technological and biological systems. Nodes in such networks organize into densely linked and overlapping clusters that correspond to communities in social networks, functionally related proteins in biological networks, or topically related webpages in information networks. Identifying such clusters is crucial to the understanding of the structural and functional roles of networks.

Our work stems from an intuitive observation that the probability of an edge between a pair of nodes increases with the number of shared cluster affiliations, which means that cluster overlaps are more densely connected that their non-overlapping parts. While present community detection methods fail to detect such overlaps we discuss a model-based community detection method that builds on bipartite node-community affiliation networks and allows for detecting overlapping, non-overlapping as well as hierarchically nested communities in networks. We develop a set of model inference techniques and accurately identify clusters in networks ranging from biological protein-protein interaction networks to social, collaboration and information networks. Moreover, our methods scale to networks of tens of millions of edges. Our results imply that while networks organize into overlapping communities, globally networks also exhibit nested core-periphery structure, which arises as a consequence of communities being `tiles' that overlap the most in the center of the network.

Jure Leskovec is assistant professor of Computer Science at Stanford University where he is a member of the Info Lab and the AI Lab. His research focuses on mining large social and information networks. Problems he investigates are motivated by large scale data, the Web and on-line media. This research has won several awards including best paper awards at KDD (2005, 2007, 2010), WSDM (2011), ICDM (2011) and ASCE J. of Water Resources Planning and Management (2009), ACM KDD dissertation award (2009), Microsoft Research Faculty Fellowship (2011), as well as Alfred P. Sloan Fellowship (2012). Jure received his bachelor's degree in computer science from University of Ljubljana, Slovenia, Ph.D. in machine learning from the Carnegie Mellon University and postdoctoral training at Cornell University. You can follow him on Twitter @jure.