Clustering Coefficient Queries on Massive Dynamic Social Networks
The Clustering Coefficient (CC) is a funmdamental measure in social network analysis assessing the dcgree to which nodes tend to cluster together. While CC computation on static graphs is well stud ied, emerging applications have new requirements for online query of the global CC of a given subset of a graph. As social networks are widely stored in databases for easy updating and accessing, computing CC of their subset becomes a time-consuming task, especially when the network grows large and cannot fit in melnory. This paper presents a novel method called Approximate Neighborhood Index (ANI) to sig nificantly reduce the query latency for CC computation compared to traditional SQL based database queries. A Bloomfilter-like data struc ture is leveraged to construct ANI in front of a relational database. Ex perimental results show that the proposed approach can guarantee the correctness of a CC query while significantly reducing the query latency at a reasonable memory cost.
Zhiyu Liu Chen Wang Qiong Zou Huayong Wang
IBM Research - China
国际会议
11th International Conference,WAIM 2010(第十一届网络时代管理国际会议)
九寨沟
英文
115-126
2010-07-14（万方平台首次上网日期，不代表论文的发表时间）