简单点，师兄想要生成具有power-law度分布的网络，发现当网络节点数较小的时候可能发生自连或重连。
扩展开去，对于任意的度分布，能否有一个通用的可终止的算法来产生这样一个网络？对于某一度分布参数的度序列，很显然必须有以下两个要求：总的度为偶数（无向网络决定的）；度介于1到N-1之间，N为网络大小。这篇文章描述了一种算法来实现。注意，文中提到如果发生自连或重连就重新来过。这样的算法是无法判断可否停机的，无法忍受啊。
我想到了一个算法来消除自连，基本的思路就是每步总是先让剩余度大的节点随机长出边。下面是一个简单的R语言实现。
N <- 4
rand <- function(n=1,N){
round(runif(n,min=0.5,max=N+0.5))
}
net <- matrix(0,N,N)
# degree <- degree.bak
degree <- rand(N-1,N-1)
degree <- c(ifelse(sum(degree)%%2==0, 2, 1),degree)
#degree.bak <- degree
degrees <- sum(degree)
while(degrees!=0){
id <- which(degree==max(degree))
id <- id[rand(1,length(id))]
pos <- setdiff(which(degree!=0),c(id,which(net[id,]==1)))
pos <- pos[rand(1,length(pos))]
net[id,pos] <- net[id,pos] <- 1
degree[c(id,pos)] <- degree[c(id,pos)]-1
degrees <- degrees-2
}
然后我就发现自连好像解决了，但是还是有很多重连的情况发生。
看到一个特例才发现任意的度序列简单满足上面提到的两条规则不能保证有解。例如4个节点具有度(1,1,3,3)。
口———— ————口
| \
| \
\ |
\ |
口———— ————口
那么，什么样的度序列一定是有解的呢？ 用方程描述，即
\[\begin{aligned} x_{ij}=x_{ji} \\ x_{ij}=0|1 \\ x_{ii}=0 \sum{x_{ij}}=k_j \end{aligned}\]Update: 原来这个问题在1960年由Erdős and Gallai解决了，后人也给出了许多构造性的证明，可参考文献A short constructive proof of the Erdoős-Gallai characterization of graphic lists1。
-
A. Tripathi, S. Venugopalan, and D. B. West, Discrete Math. 310, 843 (2010). ↩