基于社区发现的社交网络影响力阻断最大化算法北大核心CSCD

随着社交网络的日益普及,社交网络已经成为信息传播的主要平台之一。由于对社交网络内容监管相对困难,导致一些负面信息容易快速扩散并产生较大的不良影响。影响力阻断最大化问题旨在寻找需要采用正影响的节点集,使信息传播过程中被负向消息影响的节点数量最小化。针对现有社交网络影响力阻断算法运行时间复杂度较高的问题,文章提出了基于社区发现的影响力阻断最大化算法,该算法首先使用社交网络节点的扩展h指数中心性来选择候选种子节点;然后以这些种子节点为起点,利用标签传播算法发现社交网络中的社区;接着通过计算社交网络社区的关系矩阵及当前关系矩阵的模块度对社区进行合并;最后,计算初始种子节点的标签度量等级,选取前k个节点作为具有最大阻断影响力的成员。实验结果表明,该算法阻断性能好,且时间复杂度低。     

Asyn-SimRank：一种可异步执行的大规模 SimRank 算法

SimRank 算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中．近年来,随着大数据技术的发展,SimRank 算法处理的数据不断增大,人们利用MapReduce 等分布式计算模型设计实现分布式的大规模 SimRank 算法来适应大数据处理的需求．但是,由于 SimRank 算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank 算法不能在分布式环境下高效地实现．1）提出 Asyn‐SimRank 算法,该算法采用迭代‐累积的方式完成迭代计算,异步执行 SimRank 的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2）提出关键点优先调度计算,提升了 Asyn‐SimRank 算法的全局收敛速度;3）证明了 Asyn‐SimRank 算法的正确性和收敛性以及关键点优先调度计算的有效性;4）支持异步迭代的分布式框架 Maiter 上实现了 Asyn‐SimRank 算法．实验结果显示,相比较于 Hadoop ,Spark 上实现的 SimRank 算法和 Delta‐SimRank 算法,Asyn‐SimRank 算法大大提升了算法的计算效率,加速了算法收敛．     

基于随机游走相似度矩阵的改进标签传播算法

基于标签传播的社区发现算法因其时间效率高而得到广泛关注。针对该算法因标签传播的随机性导致其社区划分准确度难以保证的问题,提出一种基于随机游走的改进算法。首先,引入随机游走思想,计算得到一种衡量网络节点间相似度的矩阵;其次,在标签传播过程中,当邻居节点中标签出现频率存在多个最高时,不是随机选择一个,而是选择相似度最高的邻居节点所拥有的标签来更新,避免了标签在社区之间的任意传播;最后,用不同的真实网络进行测试,结果表明在社区发现中该算法比原始标签传播算法取得更好的表现。     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。     

一种适用于社交网络分析的分层社区检测算法

分层社区在社交网络中普遍存在,笔者针对社交网络分析中分层社区检测中容易将分层社区判定为独立社区的问题,提出一种基于层次压缩和扩展的分层社区检测算法。该算法定义了社区判定系数和聚类系数来描述节点的社区分层倾向,描述节点与社区的关系,缩小了社区检测的计算范围;通过迭代压缩、扩展等操作更新节点相关系数指标,最终算法复杂度为O(m+n)。在不损失检测质量的前提下,可以得到较好的检测效率。     

FCM框架下的重叠社区发现算法

重叠社区发现是近些年来社交网络分析中的一个热门课题,但大部分算法有着时间复杂度高或健壮性差的缺点。本文构造了一种节点相似度计算方法,针对FCM的缺陷提出改进,从而利用该改进的Fuzzyc-means计算出每个节点的隶属度;然后设定阅值决定每个节点的类别,实现了重叠社区发现;接下来在真实数据集上的对比实验结果表明该算法在有较低的时间复杂度同时能有效的发现网络中的重叠社区结构。     

节点传播能力的偏好随机行走的信息传播方法

随机行走是社交和生物系统中用来模拟传播过程的标准化工具,针对真实社交网络中任意程度的有偏随机行走过程和由优先转移概率定义的偏向性,提出了一种新的用于研究社交网络的影响力传播范围最大化的方法,称之为基于节点传播能力的偏向性随机行走的网络信息传播方法（DCID）,该方法随机从网络中选择一个信息传播源节点,使得该模型更加符合真实的社交网络;通过节点能承受的传播信息的内容量参数以及偏向性随机行走的参数来作为节点的优先转移概率;并通过影响力传播函数来衡量信息的影响力传播范围,以此达到信息传播范围的最大化。从真实的不同规模的社交网络中选定这两个参数值,并验证了提出的模型在不同规模社交网络中信息的覆盖率和算法运行时间的性能上有所提升。     

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

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

基于图结构特征分析的Top-k结构洞发现算法

结构洞通常指社交网络中处于信息扩散关键位置的节点,此类节点对社交网络舆情控制、影响力分析、信息传播等具有重要作用。为快速准确地找到社交网络中的结构洞,提出一种基于图最短路径增量的Top-k结构洞发现算法。通过计算并分析节点的图最短路径增量、连通分量个数和节点方差确定其结构洞属性值,并依据该属性值对节点进行排序,从而发现Top-k结构洞。同时,结合中介中心性算法进行节点的过滤与筛选,大幅降低算法的时间复杂度。在真实网络和不同规模LFR人工合成网络上的实验结果表明,与经典结构洞发现算法相比,该算法具有更高的结构洞检测效率。     

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

Assessing single-pair similarity over graphs by aggregating first-meeting probabilities

Link-based similarity plays an important role in measuring similarities between nodes in a graph. As a widely used link-based similarity, SimRank scores similarity between two nodes as the first-meeting probability of two random surfers. However, due to the large scale of graphs in real-world applications and dynamic change characteristic, it is not viable to frequently update the whole similarity matrix. Also, people often only concern about the similarities of a small subset of nodes in a graph. In such a case, the existing approaches need to compute the similarities of all node-pairs simultaneously, suffering from high computation cost.In this paper, we propose a new algorithm, Iterative Single-Pair SimRank (ISP), based on the random surfer-pair model to compute the SimRank similarity score for a single pair of nodes in a graph. To avoid computing similarities of all other nodes, we introduce a new data structure, position matrix, to facilitate computation of the first-meeting probabilities of two random surfers, and give two optimization techniques to further enhance their performance. In addition, we theoretically prove that the time cost of ISP is always less than the original algorithm SimRank. Comprehensive experiments conducted on both synthetic and real datasets demonstrate the effectiveness and efficiency of our approach.     

A high-performance algorithm for finding influential nodes in large-scale social networks

As one of the significant issues in social networks analysis, the influence maximization problem aims to fetch a minimal set of the most influential individuals in the network to maximize the number of influenced nodes under a diffusion model. Several approaches have been proposed to tackle this NP-hard problem. The traditional approaches failed to develop an efficient and effective solution due to the exponential growth of the size of social networks (due to massive computational overhead). In this paper, a three-stage framework based on the community detection approach is devised, namely LGFIM. In the first stage, the search space was controlled by partitioning the network into communities. Simultaneously, three heuristic methods were presented for modifying the community detection algorithm to extract the optimal communities: core nodes selection, capacity constraint on communities, and communities combination. These extracted communities were highly compatible with the information propagation mechanism. The next stages apply a scalable and robust algorithm at two different levels of the network: 1. Exploring the local scope of communities to select the most influential nodes of each community and construct the potential influential nodes set 2. Exploring the global scope of the network to select the target influential nodes among potential influential nodes set. Experimental results on various real datasets proved that LGFIM could achieve remarkable results compared with the state-of-the-art algorithms, especially acceptable influence spread, much better running time, and more applicable to massive social networks.

     

基于仿射传播的有向网络聚类算法

现有大多数的网络聚类方法都只是针对无向网络, 已有的有向网络聚类方法建立在传统聚类算法基础之上, 存在着一定的局限性。针对上述问题, 提出一种基于仿射传播的有向网络聚类算法, 该算法首先采用SimRank作为节点之间的相似度, 并将计算得到的结果转换为适应于仿射传播算法的负值; 然后将相似度矩阵作为输入, 利用具有更好性能的仿射传播算法对有向网络进行聚类。实验结果表明, 所提出算法的聚类性能优于其他几种具有代表性的有向网络聚类算法。     

信息网络中一个有效的基于链接的结点相似度度量

信息网络无处不在.通过把网络中的对象抽象为点,把对象之间的关系刻画为边,相应的信息网络就可以用图来表示.图中结点相似度计算是图数据管理中的基本问题,在很多领域都有运用,比如社会网络分析、信息检索和推荐系统等.其中,著名的相似度度量是以Personalized PageRank和SimRank为代表.这两种度量本质都是以图中的路径来定义,然而它们侧重的路径截然不同.为此,提出了一个度量 SuperSimRank.它不仅涵盖了这些路径,而且考虑了Personalized PageRank和SimRank两者都没有考虑的路径,从而能够更加体现出这种链接关系的本质.在此基础上对SuperSimRank进行了理论分析,从而提出了相应的优化算法,使得计算性能从最坏情况O(kn4)提高到O(knl).这里,k 是迭代次数,n 是结点数,l 是边数.最后,通过实验验证了 SuperSimRank 优于 SimRank 和 Personalized PageRank,同时验证了优化算法在各种情况下都是有效的.     

面向GPU平台的复杂网络core分解方法研究

在复杂网络理论中,core分解是一种最基本的度量网络节点“重要性”并分析核心子图的方法.Core分解广泛应用于社交网络的用户行为分析、复杂网络的可视化、大型软件的代码静态分析等应用.随着复杂网络的图数据规模和复杂性的增大,现有研究工作基于多核CPU环境设计core分解并行算法,由于CPU核数和内存带宽的局限性,已经无法满足大数据量的高性能计算需求,严重影响了复杂网络的分析应用.通用GPU提供了1万以上线程数的高并行计算能力和高于100GB/s访存带宽,已被广泛应用于大规模图数据的高效并行分析,如广度优先遍历和最短路径算法等.为了实现更为高效的core分解,提出面向GPU平台下的复杂网络core分解的两种并行策略.第1种RLCore策略基于图遍历思想,利用GPU高并发计算能力对网络图结构自底向上遍历,逐步迭代设置各节点所属的core层;第2种ESCore策略基于局部收敛思想,对各节点从邻居节点当前值进行汇聚计算更新直至收敛.ESCore相比RLCore能够大大降低遍历过程中GPU线程更新同一节点的同步操作开销,而其算法的迭代次数受收敛率的影响.在真实网络图数据上的实验结果表明,所提出的两个策略在效率和扩展性方面能够大幅优于现有其他方法,相比单线程上的算法高达33.6倍性能提升,且遍历边的吞吐性能(TEPS)达到406万条/s,单轮迭代的ESCore的执行效率高于RLCore.     

D-HOCS: an algorithm for discovering the hierarchical overlapping community structure of a social network

Social networks often demonstrate a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities, i.e. communities in social networks may be overlapping. In this paper, we define a hierarchical overlapping community structure to present overlapping communities of a social network at different levels of granularity. Discovering the hierarchical overlapping community structure of a social network can provide us a deeper understanding of the complex nature of social networks. We propose an algorithm, called D-HOCS, to derive the hierarchical overlapping community structure of social networks. Firstly, D-HOCS generates a probability transition matrix by applying random walk to a social network, and then trains a Gaussian Mixture Model using the matrix. Further D-HOCS derives overlapping communities by analyzing mean vectors of the Gaussian mixture model. Varying the number of components, D-HOCS repeatedly trains the Gaussian mixture model, detecting the overlapping communities at different levels of granularity. Organizing the overlapping communities into a hierarchy, D-HOCS can finally obtain the hierarchical overlapping community structure of the social network. The experiments conducted on synthetic and real dataset demonstrate the feasibility and applicability of the proposed algorithm. We further employ D-HOCS to explore Enron e-mail corpus, and obtain several interesting insights. For example, we find out a coordinator who coordinated many sections of the Enron Corporation to complete an important task during first half of 2001. We also identify a community that corresponds to a real organization in Enron Corporation.     

一种基于交互迭代式的多尺度社团发现算法研究

社团发现是复杂网络研究领域的重要研究内容之一。为了提高社团发现的性能,本文提出了一种交互迭代式的多尺度社团发现算法。将网络中的社团定量描述为邻居节点、外来节点和重叠节点多个尺度的线性组合,并针对每个尺度给出了相应的矩阵计算描述。在应用上述定量描述指标对网络进行社团发现时,提出了一种包含两个阶段的迭代式社团发现算法。在这两个阶段中,分别固定社团集合和主社团集合,并且分别调整主社团集合和社团集合来最大化上述社团量化指标。实验表明,本文提出的算法与其它社团发现算法相比不仅准去性和效率高,而且具有很好的灵活性     

Local community detection algorithm based on local modularity density

Compared to global community detection, local community detection aims to find communities that contain a given node. Therefore, it can be regarded as a specific and personalized community detection task. Local community detection algorithms based on modularity are widely studied and applied because of their concise strategies and prominent effects. However, they also face challenges, such as sensitivity to seed node selection and unstable communities. In this paper, a local community detection algorithm based on local modularity density is proposed. The algorithm divides the formation process of local communities into a core area detection stage and a local community extension stage according to community tightness based on the Jaccard coefficient. In the core area detection stage, the modularity density is used to ensure the quality of the communities. In the local community extension stage, the influence of nodes and the similarity between the nodes and the local community are utilized to determine boundary nodes to reduce the sensitivity to seed node selection. Experimental results on real and artificial networks demonstrated that the proposed algorithm can detect local communities with high accuracy and stability.

     

基于拓扑特征的二分网络社团结构划分

目前社团结构划分算法只能划分1类节点并且依赖于额外参数。为此,在分析二分网络社团拓扑特征的基础上,利用社团核与外层的思想,提出一种新的社团结构划分算法。该算法完全依赖于原始网络本身的拓扑结构,并且允许社团间重叠。实验结果表明,该算法无需任何额外参数,即可比较准确地识别实际网络的社团个数,同时划分2类节点的社团结构。