基于不同划分优度的因特网拓扑聚合特征

Community clustering features in internet topology based on different quality functions

因特网拓扑的社区聚合特征对网络性能具有重要影响.本文选取两种不同的社区划分算法:基于模块度Q的MOME算法与基于伸缩变换覆盖测度SCM的SACA算法,利用10年实际测量数据,对因特网AS层拓扑分别进行社区划分,获得的社区结构具有显著差异,究其根源在于两种算法采用的社区划分优度不同.分析发现:微小社区占大多数的幂律分布以及社区结构以星型为主的现象是SCM测度自身限制的效果.基于模块度Q的社区划分显示因特网拓扑聚合程度显著且呈增长趋势,社区规模随网络规模增长,社区结构以稠密的非星结构为主.研究表明,设计适当的社区划分优度及划分算法对于正确理解实际网络真实聚合特征具有重要意义.

Clustering features in Internet topology have important effects on network performance.Two clustering algorithms MOME and SACA which are respectively based on different partition quality functions,the modularity Q and the scaled cover measure（SCM）,are chosen to discover the clustering features in AS-level Internet topologies.The partition quality functions are shown to be the origin of the dramatically different community structures returned from different algorithms.The reported community size power-law and the majority small communities as well as the star communities in AS topology are shown to be the artifacts of the quality function SCM.Whereas the modularity Q leads to reveal that the AS topology modularity is increasingly remarkable,the community sizes grow with network size,and the majority communities are large,dense and local.This work shows that the appropriate partition quality function and the clustering algorithm are of great relevance for understanding the genuine clustering features of actual networks.