Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient
Generalized Attachment Models for the Genesis of Graphs with High Clustering Coefficient
复制标题
高聚类系数图生成的广义依附模型
DOI：
10.1007/978-3-642-01206-8_9
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
J. Gustedt
中科院分区：
文献类型：
--
作者：
J. Gustedt
常用的随机图生成技术，如Erdő，S和Barabási&Albert的方法，有两个缺点，一是对图的演化历史缺乏偏见，二是不能产生具有非零聚类系数的图族。在这项工作中，我们提出了一个图的起源模型，解决了这两个问题。当转化为随机生成过程时，它推广了上述过程。当仅仅被看作是图的合成方案时，它们推广了弦图的完美消去方案。该模型迭代地添加所谓的上下文，该上下文引入了对图的先前演化的显式依赖。因此，它们反映了这种演变过程中的历史偏见，这种偏见超越了偏好边缘依附的简单程度限制。在起源过程中固定某些简单的静态量会导致随机图族的聚类系数可以从零有界。
Commonly used techniques for the random generation of graphs such as those of Erdős & Rényi and Barabási & Albert have two disadvantages, namely their lack of bias with respect to history of the evolution of the graph, and their incapability to produce families of graphs with non-vanishing prescribed clustering coefficient. In this work we propose a model for the genesis of graphs that tackles these two issues. When translated into random generation procedures it generalizes the above mentioned procedures.When just seen as composition schemes for graphs they generalize the perfect elimination schemes of chordal graphs. The model iteratively adds so-calledcontextsthat introduce an explicit dependency to the previous evolution of the graph. Thereby they reflect a historical bias during this evolution that goes beyond the simple degree constraint of preference edge attachment. Fixing certain simple statical quantities during the genesis leads to families of random graphs with a clustering coefficient that can be bounded away from zero.