Graph models for self-organizing networks

点击翻译按钮获取中文摘要

The last decade has seen increased interest in the structure of self-organizing networks such as the World Wide Web, social networks,  and biological networks: for example those formed by the interactions of proteins in a cell. This interest has opened up a new direction of study in graph theory, which combines elements of the theory of random graphs, structural graph theory, graph clustering, and infinite graphs. In addition, some of the techniques that need to be employed to model these real-life networks are akin to those used in the natural sciences, but are not part of traditional graph theory: exploration of the data, development and analysis of stochastic models, and validation of the models.My current research interest lies in the analysis of those stochastic graph models that I consider the most promising. In particular, I intend to continue my study of the "generalized copy model". This model is based on the evolutionary principle of duplication and error. New nodes joining the graph "copy" each of the links of an existing node with a certain probability, and then add a pre-defined number of randomly chosen extra "error" links. A promising new tool to analyze this and other models is the study of the infinite limit of the model.A second class of models that hold my interest are models that have a "geometric" component. This means that each node corresponds to a point in some Euclidean space, and its attachment to the rest of the graph is influenced by its geometric position with respect to other nodes. Geometric models seem to have many features that correspond to those observed in real- life self-organizing networks. In particular, I would like to study the possibility of "reverse engineering" a graph generated according to geometric principles: given a graph that is assumed to be generated according to a certain geometric model, is it possible to estimate the position of the corresponding points? Solving this problem would give rise to new tools to extract community structure in social networks, better Web search methods, and generally give us a better understanding of networked data.