Graph models for self-organizing networks

在过去的十年里，人们对自组织网络的结构越来越感兴趣，如万维网、社交网络和生物网络：例如那些由细胞中蛋白质相互作用形成的网络。这种兴趣开辟了一个新的研究方向，在图论，它结合了元素的理论，随机图，结构图理论，图聚类和无限图。此外，一些需要用来模拟这些现实生活中的网络的技术类似于自然科学中使用的技术，但不是传统图论的一部分：数据的探索，随机模型的开发和分析，以及模型的验证。我目前的研究兴趣在于分析那些我认为最有前途的随机图模型。特别是，我打算继续我的研究“广义复制模型”。该模型基于重复和错误的进化原理。加入图的新节点以一定的概率“复制”现有节点的每个链接，然后添加预定义数量的随机选择的额外“错误”链接。一个很有前途的新工具来分析这个模型和其他模型是研究模型的无限极限。第二类模型，我感兴趣的是有一个“几何”组件的模型。这意味着每个节点对应于某个欧几里得空间中的一个点，它与图的其余部分的连接受到它相对于其他节点的几何位置的影响。几何模型似乎有许多特征与在真实的自组织网络中观察到的特征相对应。特别是，我想研究“逆向工程”根据几何原理生成的图形的可能性：给定一个假设根据某种几何模型生成的图形，是否可能估计出相应点的位置？解决这个问题将产生新的工具来提取社交网络中的社区结构，更好的Web搜索方法，并通常使我们更好地了解网络数据。

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.