基于位置的社交网络中双重异质社区的聚类与关联方法

Clustering and Associating Method of Dual Heterogeneous Communities in Location Based Social Networks

近年来,异质信息网络特别是基于位置的社交网络(Location-Based Social Networks,LBSN)中的社区发现已成为新兴的研究热点.然而,目前大多数社区发现研究仅考虑基于同质结构的社交网络,显然都已无法有效融合LBSN这种异质网络所包含的多模实体及其多维关系.为了应对该挑战性问题,本文提出了一种新的双重社区聚类与关联方法(Communities Clustering and Associating Method,CCAM),该方法先在LBSN的社交媒体层上,通过信息熵度量用户发布主题之间的相似性,进而再将相似用户兴趣聚类问题转换成求解基于模糊聚类的目标函数以获得重叠的兴趣主题簇结构.然后在地理位置层中,将用户-位置签到关系网络形成的二分图转换为超图模型,并采用超边聚类方式得到用户关于地理位置的兴趣点特征簇.最后,在兴趣主题簇与地理位置簇之间借助中间用户层的社交关系建立这两层异质簇间的关联性表示模型,并通过随机梯度下降法求解模型的局部最优解.在两个真实数据集Foursquare(NYC)和Yelp上的实验结果表明,本文提出的CCAM方法有效融合了用户-媒体发布关系、用户间社交关系、用户-位置签到关系等多维度关系,能准确获得LBSN中紧密关联的用户兴趣主题簇与地理位置簇,使得这双层社区结构不仅在外部结构特征与兴趣内聚性指标上都优于传统算法,并且还在兴趣主题推荐与位置兴趣点推荐方面的平均准确率提高至少32%.

In recent years,community discovery in heterogeneous information networks,especially in location-based social networks(LBSN),has become an emerging research hotspot attracting more and more attentions.However,since presently most of the traditional community discovery studies in social networks only focus on homogeneous network structures,there exists one obvious drawback in these studies that they cannot effectively integrate the multi-mode entities and their multi-dimensional heterogeneity relations included in LBSN.Therefore,in order to overcome this challenging problem,this paper proposes a novel dual heterogeneous communities clustering and associating method,which is called CCAM to fully fuse with multi-mode entities and their multi-relations.The main idea of CCAM is below:firstly,in the upper social media layer of LBSN,this method measures the similarity of publishing document topics between users by means of information entropy,and further transforms the similar interests clustering problem into solving the objective function based on fuzzy clustering to identify the overlapping topic-based communities of users.Then,in the bottom geographical location layer,the bipartite graph between users and locations with check-ins relationships is converted to the hyper graph model,and the proposed hyper edge clustering approach based on graph partition is exploited to obtain the point of interest clusters about geographical features of users.Finally,the representation model for associating the upper topic-based communities and the bottom geographical location clusters is established via users’social relations in the middle user layer of LBSN,and the local optimal solution of association function for the dual heterogeneous clusters is gained by using stochastic gradient descent method.The experimental results in two real LBSN datasets such as Foursquare(NYC)and Yelp show that our proposed CCAM method can effectively fuse three types of relations in LBSN,for example,social relations of users,social media publishing relations,and users check-ins relations.Consequently,this method can accurately obtain the closely correlated dual heterogeneous clusters such as the user’s interest clusters and geographical location clusters,which not only makes the external structural characteristic and the internal interest cohesive index better than some traditional community clustering algorithms,but also outperforms these algorithms at least 32%through measuring the mean average precision in the both field of online interest topics recommendation and offline point of interest recommendation.