Detecting community structure in networks by representative energy

Network community has attractedmuch attention recently, but the accuracy and efficiency in finding a community structure is limited by the lower resolution of modularity. This paper presents a new method of detecting community based on representative energy. The method can divide the communities and find the representative of community simultaneously. The communities of network emerges during competing for the representative among nodes in network, thus we can sketch structure of the whole network. Without the optimizing by modularity, the community of network emerges with competing for representative among those nodes. To obtain the proximate relationships among nodes, we map the nodes into a spectral matrix. Then the top eigenvectors are weighted according to their contributions to find the representative node of a community. Experimental results show that the method is effective in detecting communities of networks.     

一种基于局部信息的社区发现方法

针对复杂网络中难以发现小社区的问题,在CNM算法的基础上,提出一种利用局部信息进行社区挖掘的方法。定义节点的强度及节点对社区的贡献,改进模块度使该方法能适用于带权网络。利用社区局部信息得到小社区集合,将小社区集合作为CNM算法的输入,计算小社区间的模块度增量,凝聚模块度增量小的小社区,并得到最终结果。实验结果表明,该方法具有较高的社区模块度和算法执行 效率。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

MSNV:基于多层次社团划分的网络结构可视化方法

针对大规模网络节点数目庞大、结构复杂性高,有限的屏幕空间难以展示其结构特征的问题,提出了一种基于社团划分的多层次网络可视化方法。首先,使用基于网络模块度的社团划分算法对网络节点进行划分,并采用贪婪算法寻找最大模块度的社团划分,得到不同层次粒度的社团;其次,通过设置层次约束力以改进经典力导引算法(FDA),使改进的算法能对不同层次粒度的社团实现分层布局,解决FDA无法展示网络节点层次性的问题;最后,使用多窗口视图、Overview+Detail等交互方法分别展示高层社团和底层节点,实现兼顾网络高层次宏观结构和低层次局部细节的显示。仿真实验中,该算法的社团划分相较于自包含GN算法在效率和准确率上有所提高。案例分析表明,所提方法在大规模网络结构的显示和交互方面具有良好的效果和性能。     

基于亲密度和吸引力的二分网络社区发现算法

社区划分是二分网络研究中的一个热门话题,针对现有的二分网络社区发现算法存在从不同节点出发社区划分准确率低的问题,提出了基于亲密度和吸引力的二分网络社区发现算法（Intimacy and Attraction Algorithm,IAA）。该算法将[U]类中的每一个节点看作一个社区,通过计算出每一个社区的亲密度和社区间的吸引力来合并社区,从而得到[U]类节点的划分,最后[V]类节点划分到已有的社区中得到完整的社区划分结果。在人工数据集和真实网络上进行分析,分别利用互信息和模块度作为评价指标,实验结果表明,IAA能够更有效挖掘二分网络社区结构,具有良好的社区划分效果。     

基于随机游走的语义重叠社区发现算法

语义社会网络是由信息节点及社会关系构成的一类新型复杂网络,因此语义社会网络重叠社区发现是传统社区发现研究的新方向.针对这一问题,提出基于随机游走的语义社会网络重叠社区发现算法,该算法首先以LDA(latent Dirichlet allocation)算法为基础建立语义空间,实现节点语义信息到语义空间的量化映射;其次,以语义空间中节点信息熵作为节点语义信息比重,以节点的度分布比率作为节点关系比重,建立节点语义影响力模型及语义社会网络的加权邻接矩阵;再次,以语义影响力模型和加权邻接矩阵为参数,提出一种改进的语义社会网络重叠社区发现的随机游走策略,并提出可度量语义社区发现结果的语义模块度模型;最后,通过实验分析,验证了所提出的算法及语义模块度模型的有效性和可行性.     

基于复杂网络社区划分的网络拓扑结构可视化布局算法

许多真实的网络都可以用复杂网络的思想进行研究和解释,而社区结构是复杂网络的一个重要特征.为此,提出一种基于社区结构的网络布局算法.首先利用复杂网络社区发现算法对网络中的节点进行社区划分,并将一个社区抽象为一个节点,以社区间的关联为边构建新的网络;在此基础上,运用物理类比方法确定社区中心点的位置,并根据社区的规模确定社区的区域范围;最后运用条件择优的方式填充社区内部节点以完成网络拓扑的布局.仿真实验结果证明,该算法与传统的可视化布局算法相比,具有计算量更少、收敛速度快、结构清晰的特点,更具有实际应用的价值.     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

带源节点的快速社区发现算法

提出了一种改进的带源节点的CNM快速社区发现算法,用于含有部分已知社区属性节点的复杂网络的社区结构划分。算法中将这部分节点作为源节点,采用模块度增量最大化为目标函数对待划分节点进行聚合,并在取得最大全局模块度值时得到社区划分结果。以深圳市手机基站用户流量网络为例,将位于各规划城市中心的基站点作为源节点引入,对城市进行区域划分。结果表明,该算法不但能够发现基于各城市中心的服务边界,也能发现一些隐含的城市区域。     

基于K-means聚类算法的复杂网络社团发现新方法

提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

一种面向语义重叠社区发现的Link-Block算法

语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.     

基于孤立节点分离策略的改进鲁汶算法

鲁汶算法（LM）是基于模块度优化的复杂网络社区发现算法,有关模块度的现有研究中没有计算节点离开原属社区后模块度增益的方法。针对这一不足,基于模块度的定义和节点合并后模块度增益的计算方法,推导出了节点离开原属社区后模块度增益的计算方法,完善了该领域的理论研究。针对鲁汶算法对存储空间需求高的缺点,提出了基于孤立节点分离策略的改进鲁汶算法,该算法在每次迭代中将输入网络的孤立节点提前分离出去,只令其中的连通节点实际参与迭代过程,并在存储社区发现结果时将孤立节点和非孤立节点分开存储。基于真实网络的相关实验结果表明,采用孤立节点分离策略的改进方法,使算法对存储空间的需求减少了40%以上,并进一步缩短了算法的运行时间。因此,改进后的算法在处理真实网络时更具优势。     

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.     

基于K means聚类算法的复杂网络社团发现新方法*

提出了一种基于Kmeans 聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了Kmeans 聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

改进的CNM算法对加权网络社团结构的划分

为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法（CNM算法）。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。     

一种基于多维遗传算法的重叠社区发现方法*

社区结构的发现是社交网络分析研究的重要内容,与传统的重叠社区不同,最近的研究表明某些真实网络中在社区重叠部分要比社区内部节点间的连接更加密集,而现有的算法没有考虑此类社区结构。基于遗传算法,提出了一个新颖的方法来发现此类社区划分。为了刻画节点属于多个社区的重叠现象,首次将多维染色体和均匀块交叉算子引入到社区发现算法中。通过实验证明,提出的算法可以很好地发现社交网络中重叠和非重叠的社区结构。     

A Community Structure‐Based Approach for Network Immunization

We propose a community structure‐based approach that does not require community labels of nodes, for network immunization. Social networks have been widely used as daily communication infrastructures these days. However, fast spreading of information over networks may have downsides such as computer viruses or epidemics of diseases. Because contamination is propagated among subgraphs (communities) along links in a network, use of community structure of the network would be effective for network immunization. However, despite various research efforts, it is still difficult to identify ground‐truth community labels of nodes in a network. Because communities are often interwoven through intermediate nodes, we propose to identify such nodes based on the community structure of a network without requiring community labels. By regarding the community structure in terms of nodes, we construct a vector representation of nodes based on a quality measure of communities. The distribution of the constructed vectors is used for immunizing intermediate nodes among communities, through the hybrid use of the norm and the relation in the vector representation. Experiments are conducted over both synthetic and real‐world networks, and our approach is compared with other network centrality‐based approaches. The results are encouraging and indicate that it is worth pursuing this path.     

Detecting Overlapping Community Structures in Networks

Community structure has been recognized as an important statistical feature of networked systems over the past decade. A lot of work has been done to discover isolated communities from a network, and the focus was on developing of algorithms with high quality and good performance. However, there is less work done on the discovery of overlapping community structure, even though it could better capture the nature of network in some real-world applications. For example, people are always provided with varying characteristics and interests, and are able to join very different communities in their social network. In this context, we present a novel overlapping community structures detecting algorithm which first finds the seed sets by the spectral partition and then extends them with a special random walks technique. At every expansion step, the modularity function Q is chosen to measure the expansion structures. The function has become one of the popular standards in community detecting and is defined in Newman and Girvan (Phys. Rev. 69:026113, 2004). We also give a theoretic analysis to the whole expansion process and prove that our algorithm gets the best community structures greedily. Extensive experiments are conducted in real-world networks with various sizes. The results show that overlapping is important to find the complete community structures and our method outperforms the C-means in quality.     

融合拓扑势的社交网络层次化社区发现算法

社交网络的社区结构呈现层次性。针对传统凝聚式层次化社区发现算法效率不高以及生成的层次谱图复杂的问题，提出一种融合拓扑势的层次化社区发现算法，利用拓扑势场呈现的自然峰谷结构揭示社交网络社区间的层次关系。该算法搜索局部极大势值节点，并根据局部极大势值节点完成社区的初始划分；根据局部极大势值节点间的距离对初始社区进行迭代合并，直到所有社区被合并为一个社区。在真实社交网络和人工网络上的实验结果表明，该算法能够高效地发现社区的层次结构，生成的层次谱图简单直观。