Community mining from signed social networks
Community mining from signed social networks
复制标题
来自签名社交网络的社区挖掘
DOI：
10.1109/tkde.2007.1061
复制
发表时间：
2007-10-01
影响因子：
8.9
通讯作者：
Liu, Jiming
中科院分区：
文献类型：
--
作者：
Yang, Bo;Cheung, William K.;Liu, Jiming
现实世界中的许多复杂系统都可以建模为既包含正负关系又包含正负关系的符号社会网络。过去已经开发了挖掘社交网络的算法；然而，大多数算法主要是针对只包含正向关系的网络而设计的，因此不适合于签约网络。在这项工作中，我们提出了一种新的算法，称为FEC，用于挖掘具有正向组内关系和负向组间关系稠密的符号社会网络。FEC将关系的符号和密度都作为聚类属性，使得它不仅对符号网络有效，而且对只包含正关系的传统社会网络也有效。此外，FEC采用了基于代理的启发式算法，使算法高效(相对于网络大小的线性时间)，并能够给出近乎最优的解。FEC只依赖于一个参数，其值可以很容易地设置，并且不需要关于隐藏社区结构的先验知识。FEC的有效性和有效性已经通过一系列涉及基准签名网络和随机生成签名网络的严格实验得到了验证。
Many complex systems in the real world can be modeled as signed social networks that contain both positive and negative relations. Algorithms for mining social networks have been developed in the past; however, most of them were designed primarily for networks containing only positive relations and, thus, are not suitable for signed networks. In this work, we propose a new algorithm, called FEC, to mine signed social networks where both positive within-group relations and negative between-group relations are dense. FEC considers both the sign and the density of relations as the clustering attributes, making it effective for not only signed networks but also conventional social networks including only positive relations. Also, FEC adopts an agent-based heuristic that makes the algorithm efficient (in linear time with respect to the size of a network) and capable of giving nearly optimal solutions. FEC depends on only one parameter whose value can easily be set and requires no prior knowledge on hidden community structures. The effectiveness and efficacy of FEC have been demonstrated through a set of rigorous experiments involving both benchmark and randomly generated signed networks.