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难问题，用数学描述：

$$\begin{array}{*{20}l} {\mathop {\max }\limits_{S} } & {J(S) = \sum\limits_{{j = 1}}^{s} {D(v_{j} )} } \\ {{\text{s}}{\text{.t}}{\text{.}}} & {v_{j} \in c_{i} ,} \\ {} & {c_{i} \in \{ c_{1} , \ldots c_{k} \} } \\ \end{array}$$

其中$s$是子集大小。

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

$$\begin{array}{ll} J(S) = 0 & \\ \hbox{While} \left\vert{S}\right\vert< s & \\ \mathop{\max}\limits_{S} & J(S) := J(S) + \sum\limits_{j=1}^{s^{t}} D(v_{j}) \\ \hbox{s.t.} & N(v_{j}) \rightarrow \hbox{deactivated, iteration t}, \\ & N(v_{j}) \rightarrow \hbox{activated, iteration t+1}, \end{array}$$

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

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

时间复杂度
为选择第一个degree最高点，需要排序，这个是计算复杂度最高的，即$O(nlog(n))$，排序带来的总复杂度为：$O(iter \times nlog(n))$。另一个是失效邻近点带来的计算。假设最后的结果为$S=(p_1, p_2, ...p_s)$，因为每次都需要失效期邻近点，所以计算复杂度为$O(\sum _{i=1}^s N(p_i))$
这里的计算忽略同一个簇中多次出现的点，假设重复出现的点较少。

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

$$VI(U,V) = \sum_{i=1}^{k} \sum_{j=1}^r \frac{n_{ij}}{n}\log\left(\frac{n_{i}.n_{j}/n^{2}} {n_{ij}/n^{2}}\right),$$

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

CCF(Clustering coefficient)定义为[0,1]之间的向量，通过$L_1$范数进行比较。计算CCF平均差异$\frac{\sum_{v \in S} |G(v)-S(v)|}{|S|}.$转换成相似性指标，需要减一。

DD(Degree Distribution)比较原图和子图的度分度。$D(G,S) = \max_{v \in S} |F_{Y}(v) - F_{Y'}(v)|.$转换成相似性指标，需要减一。

Cov(Coverage)定义为子图中可直达的节点的数量和全部节点的比，即$\frac{|\cup_{s_{i} \in S} N(s_{i})|}{n}.$。值越大，意味着覆盖范围越广。

参考文献

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.