虚拟社群结构特征可视化呈现的社会网络布局算法研究

近年来,随着虚拟社区的发展,社会网络可视化软件逐渐走向普通社区成员的面前。然而现今社会网络可视化领域所采用的布局算法普遍与社会网络分析法相脱离,无法呈现社群结构特征。因此,提出凝聚子群布局算法与核心位置布局算法,它们分别以凝聚子群分析结果和成员整体中心度为布局依据,呈现社群子群和成员位置两种社群结构特征,并且依据实际数据给出布局效果。     

Efficient multi-scale community search method based on spectral graph wavelet

Community search is an important problem in network analysis, which has attracted much attention in recent years. As a query-oriented variant of community detection problem, community search starts with some given nodes, pays more attention to local network structures, and gets personalized resultant communities quickly. The existing community search method typically returns a single target community containing query nodes by default. This is a strict requirement and does not allow much flexibility. In many real-world applications, however, query nodes are expected to be located in multiple communities with different semantics. To address this limitation of existing methods, an efficient spectral-based Multi-Scale Community Search method (MSCS) is proposed, which can simultaneously identify the multi-scale target local communities to which query node belong. In MSCS, each node is equipped with a graph Fourier multiplier operator. The access of the graph Fourier multiplier operator helps nodes to obtain feature representations at various community scales. In addition, an efficient algorithm is proposed for avoiding the large number of matrix operations due to spectral methods. Comprehensive experimental evaluations on a variety of real-world datasets demonstrate the effectiveness and efficiency of the proposed method.     

Community Detection Using Jaacard Similarity with SIM-Edge Detection Techniques

The structure and dynamic nature of real-world networks can be revealed by communities that help in promotion of recommendation systems. Social Media platforms were initially developed for effective communication, but now it is being used widely for extending and to obtain profit among business community. The numerous data generated through these platforms are utilized by many companies that make a huge profit out of it. A giant network of people in social media is grouped together based on their similar properties to form a community. Community detection is recent topic among the research community due to the increase usage of online social network. Community is one of a significant property of a network that may have many communities which have similarity among them. Community detection technique play a vital role to discover similarities among the nodes and keep them strongly connected. Similar nodes in a network are grouped together in a single community. Communities can be merged together to avoid lot of groups if there exist more edges between them. Machine Learning algorithms use community detection to identify groups with common properties and thus for recommendation systems, health care assistance systems and many more. Considering the above, this paper presents alternative method SimEdge-CD (Similarity and Edge between's based Community Detection) for community detection. The two stages of SimEdge-CD initially find the similarity among nodes and group them into one community. During the second stage, it identifies the exact affiliations of boundary nodes using edge betweenness to create well defined communities. Evaluation of proposed method on synthetic and real datasets proved to achieve a better accuracy-efficiency trade-of compared to other existing methods. Our proposed SimEdge-CD achieves ideal value of 1 which is higher than existing sim closure like LPA, Attractor, Leiden and walktrap techniques.     

A Simultaneous Extraction of Context and Community from pervasive signals using nested Dirichlet process

Understanding user contexts and group structures plays a central role in pervasive computing. These contexts and community structures are complex to mine from data collected in the wild due to the unprecedented growth of data, noise, uncertainties and complexities. Typical existing approaches would first extract the latent patterns to explain human dynamics or behaviors and then use them as a way to consistently formulate numerical representations for community detection, often via a clustering method. While being able to capture high-order and complex representations, these two steps are performed separately. More importantly, they face a fundamental difficulty in determining the correct number of latent patterns and communities. This paper presents an approach that seamlessly addresses these challenges to simultaneously discover latent patterns and communities in a unified Bayesian nonparametric framework. Our Simultaneous Extraction of Context and Community (SECC) model roots in the nested Dirichlet process theory which allows a nested structure to be built to summarize data at multiple levels. We demonstrate our framework on five datasets where the advantages of the proposed approach are validated.     

Community mining using three closely joint techniques based on community mutual membership and refinement strategy

Community structure has become one of the central studies of the topological structure of complex networks in the past decades. Although many advanced approaches have been proposed to identify community structure, those state-of-the-art methods still lack efficiency in terms of a balance between stability, accuracy and computation time. Here, we propose an algorithm with different stages, called TJA-net, to efficiently identify communities in a large network with a good balance between accuracy, stability and computation time. First, we propose an initial labeling algorithm, called ILPA, combining K-nearest neighbor (KNN) and label propagation algorithm (LPA). To produce a number of sub-communities automatically, ILPA iteratively labels a node in a network using the labels of its adjacent nodes and their index of closeness. Next, we merge sub-communities using the mutual membership of two communities. Finally, a refinement strategy is designed for modifying the label of the wrongly clustered nodes at boundaries. In our approach, we propose and use modularity density as the objective function rather than the commonly used modularity. This can deal with the issue of the resolution limit for different network structures enhancing the result precision. We present a series of experiments with artificial and real data set and compare the results obtained by our proposed algorithm with the ones obtained by the state-of-the-art algorithms, which shows the effectiveness of our proposed approach. The experimental results on large-scale artificial networks and real networks illustrate the superiority of our algorithm.     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

基于LDA的结构-内容联合社团发现模型

在社会网络中,根据已有的连接关系和文本信息发掘社会网络中的社团不但可以将相似的用户划分在一个社团,还可以用来预测网络中潜在的连接关系。为了提高社会网络中社团发现的性能,本文提出了一种基于LDA的结构-内容联合社团发现模型。首先,对社会网络的图论描述进行转化,使其适用于LDA模型。其次,对LDA模型描述进行扩充,使其包含了用户间交互的文本信息。最后,通过Gibbs采样方法对模型的参数进行估计。实验表明,本文提出的社团发现模型与其它相关方法相比较,社团发现得到的社团不仅用户间连接的紧密度和用户共享兴趣爱好的强度高,而且可以更好地用于社会网络中潜在连接的预测。     

复杂网络中的社团结构发现方法

社团结构是真实复杂网络异质性与模块化特性的反映。深入研究网络的社团结构有助于揭示错综复杂的真 实网络是怎样由许多相对独立而又互相关联的社区形成的,使人们更好地理解系统不同层次的结构和功能,具有广泛 的实用价值。总结了目前常用的社区发现方法,包括经典的GN算法、模块度优化算法、基于网络动力学的方法以及 统计推断方法;用社区划分基准测试网络Zachary对上述算法进行了实验,对这几类算法的时间复杂度和优缺点进行 了比较分析。最后,对复杂网络的社区结构发现算法的研究进行了展望。     

A novel parallel community detection scheme based on label propagation

Community detection is one of the most important ways to reflect the structures and mechanisms of a social network. The overlapping communities are more in line with the reality of the social networks. In society, the phenomenon of some members sharing memberships among different communities reflects as overlapping communities in the networks. Dealing with big data networks, it is a challenging and computationally complex problem to detect overlapping communities. In this paper, we propose highly scalable variants of a community-detection algorithm in a parallel manner called Label Propagation with nodes Confidence (PLPAC). We introduce MapReduce into our scheme to process the big data in a parallel manner and guarantee the efficiency of community detection. We implemented the algorithm on artificial networks as well as real networks to evaluate the accuracy and speedup of the proposed method. Experimental results on datasets from different scenarios illustrate that the improved label propagation method outperforms the state-of-the-art methods in terms of accuracy and time efficiency.     

A framework for exploring organizational structure in dynamic social networks

Recent research has provided promising results relating to discovering communities within a social network. We find that further representing the organizational structure of a social network is an interesting issue that helps gain better understandings of the social network. In this paper, we define a data structure, named Community Tree, to depict the organizational structure and provide a framework for exploring the organizational structure in a social network. In this framework, an algorithm, which combines a modified PageRank and Random Walk on graph, is developed to derive the community tree from the social network. In the real world, a social network is constantly evolving. In order to explore the organizational structure in a dynamic social network, we develop a tree learning algorithm, which employs tree edit distance as the scoring function, to derive an evolving community tree that enables a smooth transition between two community trees. We also propose an approach to threading communities in community trees to obtain an evolution graph of the organizational structure, by which we can reach new insights from the dynamic social network. The experiments conducted on synthetic and real dataset demonstrate the feasibility and applicability of the framework. Based on the theoretical outcomes, we further apply the proposed framework to explore the evolution of organizational structure with the 2001 Enron dataset, and obtain several interesting findings that match the context of Enron.     

Enhancing Online Community Activity: Development and validation of the CA framework

Factors contributing to development of active communities are identified and combined into the Community Activity framework, which is useful in setting up new, or revitalizing inactive, communities. Found factors include: notifying members of new messages by e-mail, having a news section, and ability to add pictures to member profiles. During application of the framework to an inactive community, changes have been made to privacy options, polls, activity notifications, and other areas. Significant positive effects have been found in the number of visits, volume of posted messages, and number of topics. Interest of community members in both user profiles and the message board increased significantly. We conclude that the Community Activity framework is able to contribute in developing active online communities.     

基于边密度聚类的重叠社区发现算法

基于边聚类的社区发现算法以边为聚类对象,自然发现重叠社区,但也存在生成的社区集边界归属模糊、社区结构过度重叠等问题.基于此种情况,文中提出基于边密度聚类的重叠社区发现算法.首先,以边为研究对象,通过密度聚类检测连接紧密的核心边社区.然后,根据边界边归属策略将边界边划分到离它最近的核心边社区.针对孤立边,提出基于边的度与边的社区归属的孤立边处理策略,进一步处理未划分的孤立边,避免社区结构过度重叠的问题.最后,将边社区还原为节点社区,实现重叠社区的发现.在人工数据集和真实数据集上的实验表明,文中算法可以快速准确地检测复杂网络中的重叠社区.     

一种基于聚集系数的局部社团划分算法

社团划分算法是复杂网络研究中的一个热点问题.传统的复杂网络社团划分算法都必须获得全局网络的信息.随着网络规模不断增大,获得全局信息的难度随之增加;而在很多情况下只关心网络中某节点所在的局部社团.为了准确、快速地找到大规模复杂网络中的局部社团,提出了一种基于节点聚集系数性质的局部社团划分算法.该算法根据节点的连接频度,利用节点聚集系数的性质,从网络中某一待求节点开始,通过搜索邻居节点,划分该节点的社团结构.该算法只需要了解与待求节点相关的局部网络信息,在解决局部社团划分问题时其时间复杂度比传统的社团划分算法低.同时,该算法也可以应用于复杂网络全局社团结构的划分.利用该算法分别对Zachary空手道俱乐部网络和由Java开发工具包构成的软件网络图进行社团划分实验,并且分别对实验结果与对象网络的具体特征进行了对比分析.     

基于深度稀疏自动编码器的社区发现算法

社区结构是复杂网络的一个重要特征,社区发现对研究网络结构有重要的应用价值.k-均值等经典聚类算法是解决社区发现问题的一类基本方法.然而,在处理网络的高维矩阵时,使用这些经典聚类方法得到的社区往往不够准确.提出一种基于深度稀疏自动编码器的社区发现算法CoDDA,尝试提高使用这些经典方法处理高维邻接矩阵进行社区发现的准确性.首先,提出基于跳数的处理方法,对稀疏的邻接矩阵进行优化处理.得到的相似度矩阵不仅能反映网络拓扑结构中相连节点间的相似关系,同时能反映不相连节点间的相似关系.接着,基于无监督深度学习方法,构建深度稀疏自动编码器,对相似度矩阵进行特征提取,得到低维的特征矩阵.与邻接矩阵相比,特征矩阵对网络拓扑结构有更强的特征表达能力.最后,使用k-均值算法对低维特征矩阵聚类得到社区结构.实验结果显示,与6种典型的社区发现算法相比,CoDDA算法能够发现更准确的社区结构.同时,参数实验结果显示,CoDDA算法发现的社区结构比直接使用高维邻接矩阵的基本k-均值算法发现的社区结构更为准确.     

微博社区的动态节点自适应增量交互优化

大多数的社区发现方法是基于网络拓扑结构和边缘密度来进行最佳社区确定,但是这些方法具有非常高的计算复杂度,对网络的形式和类型非常敏感。为解决这些问题,提出基于动态节点自适应增量模型的微博社区交互优化算法,该算法在优化每个社区内成员的交互作用的基础上,利用贪婪算法有效地搜索最优社区的候选,无需遍历所有节点。该模型可快速、准确地测量社区内部和社区之间的交互作用差异。最后,在基准测试网络和搜狐微博平台抓取数据上的仿真测试显示,所提算法在召回率、准确率、算法计算时间以及网络覆盖率等指标上,要优于选取的对比算法。     

基于维基百科社区挖掘的词语语义相似度计算

词语语义相似度计算在自然语言处理如词义消歧、语义信息检索、文本自动分类中有着广泛的应用。不同于传统的方法,提出的是一种基于维基百科社区挖掘的词语语义相似度计算方法。本方法不考虑单词页面文本内容,而是利用维基百科庞大的带有类别标签的单词页面网信息,将基于主题的社区发现算法HITS应用到该页面网,获取单词页面的社区。在获取社区的基础上,从3个方面来考虑两个单词间的语义相似度:(1)单词页面语义关系;(2)单词页面社区语义关系;(3)单词页面社区所属类别的语义关系。最后,在标准数据集WordSimilarity-353上的实验结果显示,该算法具有可行性且略优于目前的一些经典算法;在最好的情况下,其Spearman相关系数达到0.58。     

Sustainability of Open Source software communities beyond a fork: How and why has the LibreOffice project evolved?

Many organisations are dependent upon long-term sustainable software systems and associated communities. In this paper we consider long-term sustainability of Open Source software communities in Open Source software projects involving a fork. There is currently a lack of studies in the literature that address how specific Open Source software communities are affected by a fork. We report from a study aiming to investigate the developer community around the LibreOffice project, which is a fork from the OpenOffice.org project. In so doing, our analysis also covers the OpenOffice.org project and the related Apache OpenOffice project. The results strongly suggest a long-term sustainable LibreOffice community and that there are no signs of stagnation in the LibreOffice project 33 months after the fork. Our analysis provides details on developer communities for the LibreOffice and Apache OpenOffice projects and specifically concerning how they have evolved from the OpenOffice.org community with respect to project activity, developer commitment, and retention of committers over time. Further, we present results from an analysis of first hand experiences from contributors in the LibreOffice community. Findings from our analysis show that Open Source software communities can outlive Open Source software projects and that LibreOffice is perceived by its community as supportive, diversified, and independent. The study contributes new insights concerning challenges related to long-term sustainability of Open Source software communities.     

基于统计推理的社区发现模型综述

社区有助于揭示复杂网络结构和个体间的关系.研究人员从不同视角提出很多社区发现方法,用来识别团内紧密、团间稀疏的网络结构.自2006年以来,提出了一些基于统计推理的社区发现方法,它们可识别实际网络中更多的潜在结构,并以其可靠的理论基础和优越的结构识别能力成为当前的主流.该类方法的主要目标是建立符合实际网络的生成模型以拟合观测网络,将社区发现问题转化为贝叶斯推理问题.首先给出社区发现中生成模型的相关定义;其次按照模型中社区组成元素将已有统计推理模型分为节点社区推理模型和链接社区推理模型,并深入探讨各种模型的设计思想及实现算法;再次,总结各模型适用的网络类型及规模、发现的社区结构、算法复杂度等,给出一种选择已有基于统计推理的社区发现模型的方法,并利用基准数据集对已有典型统计推理模型进行验证及分析;最后探讨了基于统计推理模型的社区发现存在的主要问题和未来发展的方向.     

A genetic search of patterns of behaviour in OSS communities

This paper proposes the identification of patterns of behaviour of open source software (OSS) communities using factor analysis and their social network analysis (SNA) features. OSS communities can be modelled as a social network in which nodes represent the community members and arcs represent the social interactions among them, and factor analysis is able to provide the factors that explain the latent patterns of behaviour. Due to the complexity of the problem and the high number of SNA features that can be extracted, this paper proposes a genetic search of an optimum subset of indicators leading to a group of latent patterns of behaviour maximizing the explained data variance and the interpretation of factors. Obtained results illustrate the feasibility of the proposed framework to extract relevant information from a large set of data.     

基于多层节点相似度的社区发现方法

社区发现是复杂网络研究中的一项重要研究内容,基于节点相似度的凝聚方法是一种典型的社区发现方法。针对现有节点相似度计算方法中存在的不足,提出一种基于多层节点的节点相似度计算方法,该方法既可以有效地计算节点之间的相似度,又可以解决节点相似度相同时的节点合并选择问题。进一步基于这种改进的节点相似度计算方法和团体之间的连接紧密度度量准则构建社区发现模型,并在真实世界的网络上进行社区发现实验。与GN算法、Fast Newman算法和改进的标签传播算法的实验结果相比,该模型可以更加准确地找到各个社区的成员。