欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
A New Approach towards Detecting Community Structures in Networks
时间  Datetime
 
地点  Venue
报告人  Speaker
Andreas Dress 教授
单位  Affiliation
中国科学院—马普学会计算生物学伙伴研究所
邀请人  Host
吴耀琨
报告摘要  Abstract
Loosely speaking, given a network consisting of a collection V of  ``nodes’’ together with some information about the degree of  relatedness between any two of its nodes, the term ``community" is  meant to refer to those subsets C of  the node set V whose  nodes are  more closely related to one another than to the nodes outside C.

Methods for detecting community structures in networks have received  much attention ever since the current network type began with the  proclamation of "scale-free" and "small-world" networks as constituting new important  and universally applicable concepts in the natural and the social  sciences.

However, a very straight-forward approach towards identifying  communities in networks published by Martin Groetschel and  Y.Wakabayashi already in 1989 was completely ignored in this context.  Using their simple basic insight, it turned out that the search for   ``good’’ community structures can be rephrased as a simple discrete-optimization problem that can be solved using well-known and widely  used linear-programming techniques.

In the lecture, I will report on joint work with William Y.C. Chen  and Winking Q. Yu from the Center for Combinatorics at Nankai  University in Tianjin (China) exploring the potential of our linear-programming based approach towards detecting community structures in  networks and, after explaining shortly how this task can be rephrased  as a discrete-optimization problem, I will present a number of  pertinent examples from the social and the life sciences and, using  artificially produced data, compare systematically the results  obtained using our approach with the results obtained by the  currently most popular methods for community detection.