今天听了实验室一个博士的论文答辩，是做关于复杂网络的社区结构研究的。原来也了解社区结构发现和一些算法，但今天才真正了解了社区结构发现算法的分类。社区结构发现包括不允许重叠和允许重叠的社区结构发现。所谓重叠，即表示某个点可同时属于多个社区。重叠节点通常有一些特别的功能和解释，例如，在论文合作网络中，可能是一个跨多个学科的研究人员。

但作者并没有讨论我最关心的问题，即复杂度问题。其实，现在的许多社区发现算法复杂度都很高，只能作用于较小的网络，对于大规模的复杂网络，提高社区发现的准确度也许并非其关键，提高社区发现的速度才是关键。Newman提出的基于Betweenness的算法，其复杂度是相当高的。如果有一种划分算法，能在不太降低准确度的情况下，数量级地提高能在单机上处理的图的规模，那我觉得其价值更大。前阵子计算所学术论文交流，看到有个做高性能计算方向的同志居然也写了一篇计算Betweenness的文章，感到很诧异，细看了一下，原来是利用多核CPU来加速Betweenness的计算的，通过适当的调度算法，可以用分布式的方式来并行计算Betweenness,从而比在单CPU上的计算速度提高了3-4倍。这个研究虽然对复杂网络的理论研究没啥帮助，但对推动其在信息领域的实用性还是有一定的价值的。

此外，虽然社区发现直觉上应该很有应用价值，但我目前还没有发现哪些领域是可以直接产生效应的, 欢迎大家探讨。