尽管带约束的聚类问题已经在无监督学习领域中得到了广泛的研究. 然而, 对于复杂网络中的社团结构探测问题, 如何将先验信息作为约束放到模型/算法中来引导探测过程仍然是一个有挑战性的问题. 在本文中, 我们提出一个半监督的网络社团结构探测框架. 这个框架根据先验信息来适当地修改网络的邻接矩阵,从而达到引导探测过程的目的. 这种修改亦可看做是对社团结构一致性矩阵的降噪和重现过程. 简言之, 我们提出的框架兼顾了网络的拓扑结构性质和网络中点的功能信息,

从而能够大幅度提高社团结构探测模型/算法的成绩. 我们将该框架应用于人工合成数据 (GN 网络和 LFR 网络) 和实际数据, 结果表明提出的框架确实能够显著提高探测成绩.  我们觉得这一框架是有趣的, 值得进一步研究.

证据表明复杂网络中经常是有社团结构的. 目前还难于对社团结构给出一个明确的和能够被广泛接受的定义, 一般认为, 网络中的社团结构指的是一个顶点集, 其内部连接是紧密的, 而与网络中其它点的连接稀疏. 社团结构经常是有特别功能和含义的, 发现网络中的社团结构对于从中观视角理解网络具有很重要的意义. 因此, 网络社团结构探测问题已经成为复杂网络分析领域中的一个热点问题. 然而, 几乎目前提出的所有模型/算法都属于无监督学习的范畴, 即意味着这些模型/算法都仅仅利用了网络本身的拓扑结构. 而在许多实际应用中, 我们经常会获得一些关于网络的背景信息和先验知识, 这些信息对于我们发现网络中的社团结构是有用的. 如何结合网络的拓扑结构性质和这些先验信息, 来引导社团结构探测过程是一个有趣的问题, 值得深入研究. 我们提出了一个半监督学习框架试图来解决此问题. 在所提出的框架下, 我们可以很容易地加入两种先验信息: i) Must-link: 即两个点必须是属于一个社团结构的; ii) Cannot-link: 即两个点一定是不属于一个社团结构的. 这两类信息我们在分析网络之前经常能够得到, 比如说, 在蛋白质相互作用网络中, 有相似功能的蛋白质就很可能是属于 Must-link的, 而在社会关系网中, 那些持不同政治观点的人就很可能是属于 Cannot-link的. 实验结果表明我们提出的框架是很有效的. 

这里需要说明的是, 我们提出的框架是独立于具体的社团结构探测模型/算法的, 即在基于我们的框架将先验信息导入邻接矩阵之后, 可以使用任何你喜欢的模型来进一步得到社团结构.

文章链接地址: 

http://iopscience.iop.org/0295-5075/101/4/48005