一个有效融合内容和链接的社区发现算法
摘要：设计一个社区发现方法挖掘在线内容网络的潜在结构，在预处理阶段基于网络的链接和节点内容属性对内容网络进行重构，基于重构网络进行链接抽样；在社区发现阶段利用概率链接模型对采样后的网络建模，并用EM算法求解模型参数，根据参数可得内容网络的潜在结构。
关键词：社区发现算法；链接分析；内容分析；概率模型
0引言
互联网出现了许多在线社交网站，用户在该平台下可发布、分享信息，吸引了越来越多的用户。
最近一些文献将此类数据建模为“内容网络（text-associated network）”，网络节点表示社交网站的用户，链接表示用户间的各种关系，不同于传统网络，节点包含内容属性，表示用户产生的内容信息。
将社交平台产生的数据建模为内容网络，挖掘其潜在结构可为基于该平台的应用服务提供依据，社区发现是一种基本的结构分析技术。
社区发现的方法很多<sup>[1]</sup>，大致分为基于链接的方法、基于内容的方法及基于链接和内容的方法。
研究表明基于链接的方法因链接存在噪音或缺失链接，导致错误的分析结果；基于内容的方法大多采用生成式模型，内容属性的不相关性使分析性能低；融合内容和链接的社区发现方法优于基于单个信息的分析。
文献[2]提出了一个有向网络的社区发现概率模型（PPL模型），对网络的有向链接生
成过程建模，并引入流行度（node popularity）变量对节点的入链（incoming links）建模，引入节点生成度（node productivity）变量对节点的出链（outgoing links）建模，最后通过EM算法求解生成模型的参数。
PPL模型是一个通用框架，可将各类概率链接分析模型统一，是目前较优的链接分析模型。
但该模型没有考虑节点的内容信息，且不能处理大型网络。
本文提出一个有效的融合内容和链接的社区发现算法，根据网络链接和内容信息进行网络抽样<sup>[3]</sup>，以适应大型网络的处理；对抽样后的网络采用PPL模型建模。
1内容网络社区发现算法
PPL模型可以准确地发现网络的潜在社区结构，但其不能处理大型网络，且没有考虑节点的内容属性。
这里将网络节点的内容属性转换到网络的链接中，并利用采样方法对网络链接进行稀疏化。
本文处理的网络记作G=（V，EL，T），其中V表示网络节点集合，E表示网络的实际链接集合，T表示节点的内容属性集合。
算法samplePPL主要步骤如下：①预处理阶段：根据网络节点的内容属性T创建内容链接集合EC；将内容链接和网络实际链接融合后的网络抽样得链接集合E；②社区发现节点：基于PPL模型对链接集合E 形成的网络建模和求解。
下面分别给出各步骤的具体实现细节。
3结语
本文提出了一个社区发现算法，其将节点的内容信息融合到网络的链接中，并利用采样方法对链接进行过滤，基于过滤的链接建立
PPL模型对节点进行划分。
该算法还有待采用更多技巧来提高速度。
参考文献：
[1]YANG TB，JIN R，CHI Y，et bining link and content for community detection：a discriminative approach[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：927936.
[2]YANG TB，CHI Y，ZHU S，et al.Directed network community detection：A popularity and productivity link model[C]//Proceedings of the SIAM Conference on Data Mining，2010：742753.
[3]RUAN YIYE，FUHRY DA VID.Parthasarathy srinivasan.efficient community detection in large networks using content and links[J].CoRR abs，2012（12）.
[4]A MCCALLUM，K NIGAM，J RENNIE，et al.Automating the construction of internet portals with machine learning[J]. J. of Info. Retr，2000（3）.。