[关闭]
@hainingwyx 2017-05-31T08:08:10.000000Z 字数 2236 阅读 788

FURS: Fast and Unique Representative Subset selection retaining large scale community structure

聚类


FURS是用于选择社区结构中具备高Degree的节点子集的算法,可用于大尺度网络中out-of-sample的算法,以外推社区亲密度。簇中心的节点对于潜在社区结构具有更好的代表性。从这来看有点类似于K-means和K-centroids作用。但是选择各个簇的中心点是一个NP难问题,因此采用了贪婪近似的方法。所采用的的策略是:首先把所有节点根据degree降序排列,选择degree最高的点,然后使其直接可达的邻居失效,然后在剩下的有效点中选择degree最高的点。重复以上,直到得到想要大小的样本子集。

相关研究

现在采样技术主要分为两个方向。节点采样和子图采样。节点采样包括:Forest-Fire和SlashBurn。子图采样包括MDD和XSN。

FURS算法

从不同的簇中选择degree最高的点,是NP难问题,用数学描述:

其中是子集大小。

一个贪婪近似解就是通过选择最高degree的点之后,使其直接可达点失效,使得焦点从网络的一个区域移动到另一个区域。如果所有点都失效了,样本集还没达到要求。重新激活所有点,重复上面过程。用数学描述这个过程:

其中FURS在t迭代时选择的节点子集的大小

算法流程
1. 中心选择
现将低于用户定义阈值和degree的中间值的点去掉,防止噪声的干扰。但是这些点的对度的贡献仍旧保留。选择中心值而非均值,也是减少噪声点的干扰。然后在剩下的子集中pop出degree最高的点
2. 失效
从待选子集中失效 ,即剩下集合可以表示为.然后选择最高degree的,并失效。失效可以保证下一个迭代选择的点不会出现在本次选择的近邻之中。
3. 激活
如果结果子图含有孤立的节点(孤立是针对结果子图而言),因为孤立节点不能体现社区结构,所以改变结果子图的大小

算法伪代码

时间复杂度
为选择第一个degree最高点,需要排序,这个是计算复杂度最高的,即,排序带来的总复杂度为:。另一个是失效邻近点带来的计算。假设最后的结果为,因为每次都需要失效期邻近点,所以计算复杂度为
这里的计算忽略同一个簇中多次出现的点,假设重复出现的点较少。

衡量标准
VI(Variation of Information)是信息衡量理论中用于比较两个不同划分结果的标准。

其中是两个不同的划分,是两个划分中簇的数量。VI的值越小,代表两个划分之间的变化越小。还有其他信息理论的评估标准如ARI和NMI。目前尚无最佳的评价标准。

CCF(Clustering coefficient)定义为[0,1]之间的向量,通过范数进行比较。计算CCF平均差异转换成相似性指标,需要减一。

DD(Degree Distribution)比较原图和子图的度分度。转换成相似性指标,需要减一。

Cov(Coverage)定义为子图中可直达的节点的数量和全部节点的比,即。值越大,意味着覆盖范围越广。

参考文献

Mall R, Langone R, Suykens J A K. FURS: Fast and Unique Representative Subset selection retaining large-scale community structure[J]. Social Network Analysis and Mining, 2013, 3(4): 1075-1095.

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注