Depoly your flask app into Heroku Fix shit IE code manually ISBN to Book Category by Scraping DangDang A Generic Makefile for C/C++ Program Configure Raspberry pi Remove watermark with PyPDF2 tips for docker Anaconda+TensorFlow+CUDA Snippets Configure Remote Mathematica Kernel Build your own ngrok server Access Array SSL VPN 使用Rstudio制作html5幻灯片 tips for Mac OS X system Tips for ipython notebook 配置Ubuntu server + Openbox (Obuntu) tips for Vimperator tips for Vim 安装CUDA My First Jekyll Blog rsync常见选项 在Linux中读取Ipod touch的文件 tip for texmacs 在VPS上建站的一些tip Gnuplot绘图札记 Samba系统和autofs自动挂载 Linux中alsamixer声卡无法录音 搭建自己的RSS订阅器——Tiny Tiny RSS Grub2引导安装Ubuntu awk tips 将Ubuntu系统装入U盘 The Great Rtorrent 编译GCC 再这样剁手!!!该死的libgd 使用ulimit进行资源限制 使用SSH代理上IPV6 使用RCurl抓取网页数据 修复Ubuntu Grub记 openbox中的文件关联 在Ubuntu 12.04下编译qtiplot 处理BCM4312网卡驱动纪实 配置我的Ubuntu Server记 Cygwin杂记 Linux 使普通用户具有以超级权限执行脚本 让firefox自定义地处理文件类型 WordPress优秀主题及插件 在phpcloud上搭建wordpress UBUNTU下用pptpd做VPN server ubuntu升级内核过后的一些问题 安装telnet服务 kubuntu札记 64位kubuntu札记 统计软件R virtualbox stardict星际译王 Ubuntu重装windows系统后的grub引导修复 SSH服务及花生壳域名解析 采用cbp2make工具由code::blocks工程创建makefile文件 UBUNTU 札记

无法生成具有任意度序列的网络

2014年05月07日

简单点,师兄想要生成具有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)。

口————    ————口
| \
|   \

          \   |
            \ |
口————    ————口

那么,什么样的度序列一定是有解的呢? 用方程描述,即

Update: 原来这个问题在1960年由Erdős and Gallai解决了,后人也给出了许多构造性的证明,可参考文献A short constructive proof of the Erdoős-Gallai characterization of graphic lists1

  1. A. Tripathi, S. Venugopalan, and D. B. West, Discrete Math. 310, 843 (2010).