LBSN中融合多维关系的社区发现方法

如何发现高质量的社区结构对于深刻研究和分析基于位置的社交网络（LBSN）这种新型复杂网络具有重要意义,然而,现有面向社交网络的社区发现方法都无法适用于具有多维异构关系的LBSN.为此,提出了一种基于联合聚类的用户社区发现方法Multi-BVD,该方法先给出了融合用户社交网络与地理位置标签网络中多模实体及其异构关系的社区划分目标函数,然后使用拉格朗日乘子法得到目标函数极小值的迭代更新规则,并运用块值矩阵分解技术来确定最优的社区划分结果.仿真实验结果表明,Multi-BVD方法能有效地发现LBSN中具有地理特征的用户社区结构,该社区结构在社交关系和地理兴趣标签上都有更优的内聚性,并能更紧密地体现用户社区与地理标签簇间的兴趣关联性.     

Cross-domain community detection in heterogeneous social networks

With the recent surge of location-based social networks (LBSNs), e.g., Foursquare and Facebook Places, huge amount of human digital footprints that people leave in the cyber-physical space become accessible, including users’ profiles, online social connections, and especially the places that they have checked in. Different from social networks (e.g., Flickr, Facebook) which have explicit groups for users to subscribe or join, LBSNs usually have no explicit community structure. Meanwhile, unlike social networks which only contain a single type of social interaction, the coexistence of online/offline social interactions and user/venue attributes in LBSNs makes the community detection problem much more challenging. In order to capitalize on the large number of potential users/venues as well as the huge amount of heterogeneous social interactions, quality community detection approach is needed. In this paper, by exploring the heterogenous digital footprints of LBSNs users in the cyber-physical space, we come out with a novel edge-centric co-clustering framework to discover overlapping communities. By employing inter-mode as well as intra-mode features, the proposed framework is able to group like-minded users from different social perspectives. The efficacy of our approach is validated by intensive empirical evaluations based on the collected Foursquare dataset.     

语义增强的大规模多元图简化可视分析方法

网络图可视化可以有效展示网络节点之间的连接关系,广泛应用于诸多领域,如社交网络、知识图谱、生物基因网络等.随着网络数据规模的不断增加,如何简化表达大规模网络图结构已成为图可视化领域中的研究热点.经典的网络图简化可视化方法主要包括图采样、边绑定和图聚类等技术,在减少大量点线交叉造成的视觉紊乱的基础上,提高用户对大规模网络结构的探索和认知效率.然而,上述方法主要侧重于网络图中的拓扑结构,却较少考虑和利用多元图节点的多维属性特征,难以有效提取和表达语义信息,从而无法帮助用户理解大规模多元网络的拓扑结构与多维属性之间的内在关联,为大规模多元图的认知和理解带来困难.因此,本文提出一种语义增强的大规模多元图简化可视分析方法,首先在基于模块度的图聚类算法基础上提取出网络图的层次结构;其次通过多维属性信息熵的计算和比较分析,对网络层次结构进行自适应划分,筛选出具有最优属性聚集特征的社团;进而设计交互便捷的多个关联视图来展示社团之间的拓扑结构、层次关系和属性分布,从不同角度帮助用户分析多维属性在社团形成和网络演化中的作用.大量实验结果表明,本文方法能够有效简化大规模多元图的视觉表达,可以快速分析不同应用领域大规模多元图的关联结构与语义构成,具有较强的实用性.     

Discovering Typed Communities in Mobile Social Networks

Mobile social networks,which consist of mobile users who communicate with each other using cell phones,are reflections of people’s interactions in social lives.Discovering typed communities(e.g.,family communities or corporate communities) in mobile social networks is a very promising problem.For example,it can help mobile operators to determine the target users for precision marketing.In this paper we propose discovering typed communities in mobile social networks by utilizing the labels of relationships between users.We use the user logs stored by mobile operators,including communication and user movement records,to collectively label all the relationships in a network,by employing an undirected probabilistic graphical model,i.e.,conditional random fields.Then we use two methods to discover typed communities based on the results of relationship labeling:one is simply retaining or cutting relationships according to their labels,and the other is using sophisticated weighted community detection algorithms.The experimental results show that our proposed framework performs well in terms of the accuracy of typed community detection in mobile social networks.     

Community detection in social networks using user frequent pattern mining

Recently, social networking sites are offering a rich resource of heterogeneous data. The analysis of such data can lead to the discovery of unknown information and relations in these networks. The detection of communities including ‘similar’ nodes is a challenging topic in the analysis of social network data, and it has been widely studied in the social networking community in the context of underlying graph structure. Online social networks, in addition to having graph structures, include effective user information within networks. Using this information leads to enhance quality of community discovery. In this study, a method of community discovery is provided. Besides communication among nodes to improve the quality of the discovered communities, content information is used as well. This is a new approach based on frequent patterns and the actions of users on networks, particularly social networking sites where users carry out their preferred activities. The main contributions of proposed method are twofold: First, based on the interests and activities of users on networks, some small communities of similar users are discovered, and then by using social relations, the discovered communities are extended. The F-measure is used to evaluate the results of two real-world datasets (Blogcatalog and Flickr), demonstrating that the proposed method principals to improve the community detection quality.     

Utilizing advances in correlation analysis for community structure detection

In the era of big data, some data records are interrelated with each other in many areas, such as marketing, management, health care, and education. These interrelated data can be more naturally represented as networks with nodes and edges. Inside this type of networks, there is usually a hidden community structure where each community represents a relatively independent functional module. Such hidden community structures are useful for many applications, such as word-of-mouth marketing, promoting decentralized social interactions inside organizations, and searching biological pathways related to various diseases. Therefore, how to detect hidden community structures becomes an important task with wide applications. Currently, modularity-based methods are widely-used among many existing community structure detection methods. They detect communities with more internal edges than expected under the null hypothesis of independence. Since research in correlation analysis also searches for patterns which occur more than expected under the null hypothesis of independence, this paper proposed a framework of changing the original modularity function according to different existing correlation functions in the correlation analysis research area. Such a framework can utilize not only the current but also the future potential research progresses in correlation analysis to advance community detection. In addition, a novel graphical analysis on different modified-modularity functions is conducted to analyze their different preferences, which are also validated by our evaluation on both real life and simulated networks. Our work to connect modularity-based methods with correlation analysis has several significant impacts on the community detection research and its applications to expert and intelligent systems. First, the research progress in correlation analysis can be utilized to define a more effective objective function in community detection for better detection results since different real-life applications might need communities with different resolutions. Second, any existing research progress for the modularity function, such as the Louvain method for speeding up the search and different extensions for overlapping community detection, can be applied in a similar way to the new objective function derived from existing correlation functions, because the new objective function is unified within one framework with the modularity function. Third, our framework opens a large unexplored area for the researchers interested in community detection. For example, what is the best heuristic search method for each different objective function? What are the characteristics of each objective function when applied to overlapping community detection? Among different extensions to overlapping community detection, which extension is better for each objective function?     

Community detection for emerging social networks

Many famous online social networks, e.g., Facebook and Twitter, have achieved great success in the last several years. Users in these online social networks can establish various connections via both social links and shared attribute information. Discovering groups of users who are strongly connected internally is defined as the community detection problem. Community detection problem is very important for online social networks and has extensive applications in various social services. Meanwhile, besides these popular social networks, a large number of new social networks offering specific services also spring up in recent years. Community detection can be even more important for new networks as high quality community detection results enable new networks to provide better services, which can help attract more users effectively. In this paper, we will study the community detection problem for new networks, which is formally defined as the “New Network Community Detection” problem. New network community detection problem is very challenging to solve for the reason that information in new networks can be too sparse to calculate effective similarity scores among users, which is crucial in community detection. However, we notice that, nowadays, users usually join multiple social networks simultaneously and those who are involved in a new network may have been using other well-developed social networks for a long time. With full considerations of network difference issues, we propose to propagate useful information from other well-established networks to the new network with efficient information propagation models to overcome the shortage of information problem. An effective and efficient method, Cat (Cold stArT community detector), is proposed in this paper to detect communities for new networks using information from multiple heterogeneous social networks simultaneously. Extensive experiments conducted on real-world heterogeneous online social networks demonstrate that Cat can address the new network community detection problem effectively.     

Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection

Outlier detection research has been seeing many new algorithms every year that often appear to be only slightly different from existing methods along with some experiments that show them to “clearly outperform” the others. However, few approaches come along with a clear analysis of existing methods and a solid theoretical differentiation. Here, we provide a formalized method of analysis to allow for a theoretical comparison and generalization of many existing methods. Our unified view improves understanding of the shared properties and of the differences of outlier detection models. By abstracting the notion of locality from the classic distance-based notion, our framework facilitates the construction of abstract methods for many special data types that are usually handled with specialized algorithms. In particular, spatial neighborhood can be seen as a special case of locality. Here we therefore compare and generalize approaches to spatial outlier detection in a detailed manner. We also discuss temporal data like video streams, or graph data such as community networks. Since we reproduce results of specialized approaches with our general framework, and even improve upon them, our framework provides reasonable baselines to evaluate the true merits of specialized approaches. At the same time, seeing spatial outlier detection as a special case of local outlier detection, opens up new potentials for analysis and advancement of methods.     

一种融合多维信息的移动社区发现方法

为解决传统社区发现算法难适用于大型复杂异质的移动网络的问题,利用移动网络使用详单数据（Usage Detail Record, UDR）和移动用户社交数据构建网络模型,提出一种融合多维信息的移动社区发现方法BNMF-NF。该方法综合考虑用户社交关系和时空行为,给出用户社交相似度、位置分布相似度和主题偏好相似度,利用加权网络融合方法融合多维相似关系构建用户相似网络,并运用有界非负矩阵分解技术实现社区结构的检测。在Foursquare和电信数据集上的实验结果表明,BNMF-NF方法能够有效发现移动网络中用户社区结构。     

Followee recommendation based on text analysis of micro-blogging activity

Nowadays, more and more users keep up with news through information streams coming from real-time micro-blogging activity offered by services such as Twitter. In these sites, information is shared via a followers/followees social network structure in which a follower receives all the micro-blogs from his/her followees. Recent research efforts on understanding micro-blogging as a novel form of communication and news spreading medium have identified three different categories of users in these systems: information sources, information seekers and friends. As social networks grow in the number of registered users, finding relevant and reliable users to receive interesting information becomes essential. In this paper we propose a followee recommender system based on both the analysis of the content of micro-blogs to detect users' interests and in the exploration of the topology of the network to find candidate users for recommendation. Experimental evaluation was conducted in order to determine the impact of different profiling strategies based on the text analysis of micro-blogs as well as several factors that allows the identification of users acting as good information sources. We found that user-generated content available in the network is a rich source of information for profiling users and finding like-minded people.     

群智感知网络中基于社会关系的社区发现算法

群智感知应用主要通过社区划分进行任务分配,然而现有群智感知应用中社区发现算法缺乏对社会关系的量化以及划分社区的特征因子单一。针对这些问题,提出了一种基于多维社会关系特征的社区发现算法,通过计算移动节点间的最优生成树、节点合并因子、社区调整因子,对移动节点的社会关系进行具体量化,将节点合理划分成不同的社区。实验结果表明,与现有方法相比,该算法在不同的数据集中具有更好的动态适应性、有效性和预测准确性,其准确性平均达到97.3%,高于对比算法15.2%。     

A framework for joint community detection across multiple related networks

Community detection in networks is an active area of research with many practical applications. However, most of the early work in this area has focused on partitioning a single network or a bipartite graph into clusters/communities. With the rapid proliferation of online social media, it has become increasingly common for web users to have noticeable presence across multiple web sites. This raises the question whether it is possible to combine information from several networks to improve community detection. In this paper, we present a framework that identifies communities simultaneously across different networks and learns the correspondences between them. The framework is applicable to networks generated from multiple web sites as well as to those derived from heterogeneous nodes of the same web site. It also allows the incorporation of prior information about the potential relationships between the communities in different networks. Extensive experiments have been performed on both synthetic and real-life data sets to evaluate the effectiveness of our framework. Our results show superior performance of simultaneous community detection over three alternative methods, including normalized cut and matrix factorization on a single network or a bipartite graph.     

Critical Nodes Identification in Large Networks: The Inclined and Detached Models

In social networks, the departure of some users can lead to the dropout of others from the community in cascade. Therefore, the engagement of critical users can significantly influence the stability of a network. In the literature, the anchored/collapsed k-core problem is proposed, which aims to enlarge/collapse the community by anchoring/deleting certain nodes. While, in real social networks, nodes are usually associated with different preferences, such as close or conflict interest. Intuitively, a community will be more stable if more nodes share close interest and fewer of them carry conflict interest. However, most existing researches simply treat all users equally, and the inclination property is neglected. To fill the gap, in this paper, we propose two novel problems, named inclined anchored k-core (IAK) problem and minimum detached k-core (MDK) problem, to better characterize the real scenarios. We prove that both problems are NP-hard. To facilitate the computation, novel search strategies are proposed. Comprehensive experiments are conducted on 9 networks to demonstrate the effectiveness and efficiency of the proposed techniques.

     

基于异构社交上下文的多视图微博主题检测

社交媒体主题检测旨在从大规模短帖子中挖掘潜在的主题信息. 由于帖子形式简短、表达非正规化, 且社交媒体中用户交互复杂多样, 使得该任务具有一定的挑战性. 前人工作仅考虑了帖子的文本内容, 或者同时对同构情境下的社交上下文进行建模, 忽略了社交网络的异构性. 然而, 不同的用户交互方式, 如转发, 评论等, 可能意味着不同的行为模式和兴趣偏好, 其反映了对主题的不同的关注与理解; 此外, 不同用户对同一主题的发展和演化具有不同影响, 社区中处于引领地位的权威用户相对于普通用户对主题推断会产生更重要的作用. 因此, 提出一种新的多视图主题模型(multi-view topic model, MVTM), 通过编码微博会话网络中的异构社交上下文来推断更加完整、连贯的主题. 首先根据用户之间的交互关系构建一个属性多元异构会话网络, 并将其分解为具有不同交互语义的多个视图; 接着, 考虑不同交互方式与不同用户的重要性, 借助邻居级注意力和交互级注意力机制, 得到特定视图的嵌入表示; 最后, 设计一个多视图驱动的神经变分推理方法, 以捕捉不同视图之间的深层关联, 并自适应地平衡它们的一致性和独立性, 从而产生更连贯的主题. 在3个月新浪微博数据集上的实验结果证明所提方法的有效性.     

一种基于因子图模型的半监督社区发现方法

社区发现是社交网络分析中一个重要的研究方向.当前大部分的研究都聚焦在自动社区发现问题,但是在具有数据缺失或噪声的网络中,自动社区发现算法的性能会随着噪声数据的增加而迅速下降.通过在社区发现中融合先验信息,进行半监督的社区发现,有望为解决上述挑战提供一条可行的途径.本文基于因子图模型,通过融入先验信息到一个统一的概率框架中,提出了一种基于因子图模型的半监督社区发现方法,研究具有用户引导情况下的社交网络社区发现问题.在三个真实的社交网络数据（Zachary社会关系网、海豚社会网和DBLP协作网）上进行实验,证明通过融入先验信息可以有效地提高社区发现的精度,且将我们的方法与一种最新的半监督社区发现方法（半监督Spin-Glass模型）进行对比,在三个数据集中F-measure平均提升了6.34%、16.36%和12.13%.     

Web-Traveler Policies for Images on Social Networks

Images are one of the most popular type of contents shared on these sites. One of the most popular types of contents shared on these sites is image. Most of these networks offer some rudimentary forms of access controls such as allowing the users to choose who can view their profiles or the images uploaded by them. These controls however apply only in the perimeter of the users’ direct control such as desktops, profiles etc. Users have no control over their content once it is downloaded by others. In order to enable a user to truly maintain control over his content, new access control mechanisms must be designed so as to enable users to control their content even when managed by others. Towards fulfilling this gap, in this paper we propose the concept of “web-traveler policies”. Web-traveler policies allow the user to specify who can view, upload or download a given image within a social network. The unique, innovative feature of web-traveler policies is that they travel with the image, as long as it is hosted on the given social networking site. Additionally, we explore the possibility of extending these controls across different sites, by using the concept of mashups. In the paper we prove the feasibility of this approach, by implementing a working prototype of our approach on a real open source social network platform. We test the performance and scalability of such architecture under heavy user loads and also its resilience towards naïve attacks. This work is a first innovative step toward scalable systems for providing each user with a centralized system for his/her own content’s protection all over the web.     

社交网Twitter平台的人物关系网社区发现

社交网络服务（social networking service,SNS）已融入到大众生活中。人们将自己的信息上传到网络中,并通过社交网站管理自己的社交圈子,由此造成大量的个人信息在社交网络上被公开。文章基于Twitter平台,设计实现了Twitter用户关系网的社区发现。通过实时采集Twitter用户信息,重建人物关系网,改进Newman快速算法划分社区发现人物关系网。文章通过可视化的界面呈现用户的社区关系,提供用户网络行为,为决策者的舆情监控或个性推荐提供了参考凭据。     

基于身份加密的机会网络安全路由架构

机会网络整合了容迟网络、移动自组织网络、社会网络等多种概念,可通过移动节点的相遇性机会实现消息的传输与共享,针对机会网络中目前较为流行的基于社会上下文的路由转发协议,设计了基于身份加密的安全架构来保证节点社会上下文的隐私性以及消息的机密性:通过可搜索的加密算法为每一个节点的社会属性设置相应的陷门,使得中继节点在可计算自...     

基于信息流动分析的动态社区发现方法

随着社交网络和微博等互联网应用的逐渐流行,其用户规模在迅速膨胀.在这些大规模网络中,社区发现可以为个性化服务推荐和产品推广提供重要依据.不同于传统的网络,这些新型网络的节点之间除了拓扑结构外,还进行频繁的信息交互.信息流动使得这些网络具有方向性和动态性等特征.传统的社区发现方法由于没有考虑到这些新的特征,并不适用于这些新型网络.在传染病动力学理论的基础上,从节点间信息流动的角度,提出一种动态社区发现方法.该方法通过对信息流动的分析来发现联系紧密、兴趣相近的节点集合,以实现动态的社区发现.在真实数据集上的实验结果表明：相对于传统的社区发现方法,所提出的方法能够更准确地发现社区,并且更能体现网络中社区的动态变化.