论文标题
在随机图属性上
On Random Graph Properties
论文作者
论文摘要
我们考虑在图理论和图形挖掘文献中感兴趣的标记随机图的15个特性，例如聚类系数，中心度测量，光谱半径，度量分类性，treedeppth，树宽，树宽等。我们分析了这些特性之间的关系和相关性。尽管对于少数顶点上的图形，我们可以准确地计算每个感兴趣属性的平均值和范围，但对于较大的图，这是不可行的。我们表明，\ Erdosrenyi Graph Generator生成的图形具有$ P = 1/2 $模型，井井有条的所有标记图的基础空间，具有固定数量的顶点。后来的观察结果使我们能够分析这些属性之间的属性和相关性，以分析较大图。然后，我们使用线性和非线性模型根据其他模型预测给定的属性，对于每个属性，我们找到了最预测的子集。我们在实验上表明，对属性的对和三元组具有很高的预测能力，从而可以估计计算在具有有效算法的属性上计算属性的昂贵。
We consider 15 properties of labeled random graphs that are of interest in the graph-theoretical and the graph mining literature, such as clustering coefficients, centrality measures, spectral radius, degree assortativity, treedepth, treewidth, etc. We analyze relationships and correlations between these properties. Whereas for graphs on a small number of vertices we can exactly compute the average values and range for each property of interest, this becomes infeasible for larger graphs. We show that graphs generated by the \ErdosRenyi graph generator with $p = 1/2$ model well the underlying space of all labeled graphs with a fixed number of vertices. The later observation allows us to analyze properties and correlations between these properties for larger graphs. We then use linear and non-linear models to predict a given property based on the others and for each property, we find the most predictive subset. We experimentally show that pairs and triples of properties have high predictive power, making it possible to estimate computationally expensive to compute properties with ones for which there are efficient algorithms.
