A new blockmodeling based hierarchical clustering algorithm for web social networks
A new blockmodeling based hierarchical clustering algorithm for web social networks
复制标题
一种新的基于块建模的网络社交网络层次聚类算法
DOI：
10.1016/j.engappai.2012.01.003
复制
发表时间：
2012-04
影响因子：
8
通讯作者：
Chen, Hongmei
中科院分区：
文献类型：
--
作者：
Qiao, Shaojie;Li, Tianrui;Li, Hong;Peng, Jing;Chen, Hongmei
随着YouTube、Facebook和TravelBlog等互联网社区的快速发展，网络社交网络的聚类分析成为一个重要而具有挑战性的问题。为了准确划分网络社交网络，我们提出了一种基于块建模的层次化聚类算法HCUBE，该算法特别适合于对链接关系复杂的网络进行聚类。HCUBE使用结构等价性来计算网页之间的相似度，将一个庞大的、不连贯的网络简化为一组更小的可理解的子网络。HCUBE实际上是一种自下而上的凝聚层次聚类算法，它利用簇的互连性和贴近度来有效地对结构相同的页面进行分组。此外，我们还讨论了所提出的区块建模的前期工作和HCUBE聚类算法的理论基础。为了提高HCUBE的效率，我们将其时间复杂度从O(|V|2)降低到O(|V|2/p)，其中p是表示初始分区数的常量。最后，我们在真实数据上进行了实验，结果表明，与变色龙算法和k-均值算法相比，HCUBE算法在划分网络社交网络方面是有效的。
Cluster analysis for web social networks becomes an important and challenging problem because of the rapid development of the Internet community like YouTube, Facebook and TravelBlog. To accurately partition web social networks, we propose a hierarchical clustering algorithm called HCUBE based on blockmodeling which is particularly suitable for clustering networks with complex link relations. HCUBE uses structural equivalence to compute the similarity among web pages and reduces a large and incoherent network into a set of smaller comprehensible subnetworks. HCUBE is actually a bottom-up agglomerative hierarchical clustering algorithm which uses the inter-connectivity and the closeness of clusters to group structurally equivalent pages in an effective fashion. In addition, we address the preliminaries of the proposed blockmodeling and the theoretical foundations of HCUBE clustering algorithm. In order to improve the efficiency of HCUBE, we optimize it by reducing its time complexity from O(|V|2) to O(|V|2/p), where p is a constant representing the number of initial partitions. Finally, we conduct experiments on real data and the results show that HCUBE is effective at partitioning web social networks compared to the Chameleon and k-means algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2004
期刊：
--
影响因子：
--
作者：
通讯作者：
--
影响因子：
--
作者：
G. Flake;R. Tarjan;Kostas Tsioutsiouliklis
通讯作者：
G. Flake;R. Tarjan;Kostas Tsioutsiouliklis
DOI：
10.3724/sp.j.1016.2008.01795
发表时间：
2009-10
期刊：
Chinese Journal of Computers
影响因子：
--
作者：
Shaojie Qiao;Changjie Tang;Jing Peng;W. Liu;Fenlian Wen;Jiangtao Qiu
通讯作者：
Shaojie Qiao;Changjie Tang;Jing Peng;W. Liu;Fenlian Wen;Jiangtao Qiu
DOI：
10.1007/978-1-4899-7687-1_348
发表时间：
2017
期刊：
--
影响因子：
--
作者：
C. Aggarwal
通讯作者：
C. Aggarwal
DOI：
10.4135/9781848608184.n22
发表时间：
2002
期刊：
--
影响因子：
--
作者：
R. Breiger;R. Breiger
通讯作者：
R. Breiger;R. Breiger