Andreas Dress 教授
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.