基于PageRank的社交网络影响最大化传播模型与算法研究

社交网络中影响最大化问题是指找出最具有影响力的k个节点,使得最终社交网络中被影响的节点最多,信息传播范围最大。针对影响最大化问题,目前已存在一些基本传播模型,但是这些模型没有考虑网络中节点的相关性和重要性,而网络中节点的相关性和重要性是衡量其影响力的一个重要指标,因此,提出了一种基于网页排名算法的信息传播模型(PageRank-based Propagation Model,PRP),然后利用贪心算法来近似求解影响最大化问题。实验结果表明,基于PageRank的传播模型解决影响最大化问题的效果比传统的线性阈值模型、加权级联模型和独立级联模型的效果更好,影响力范围更大。     

面向微博的情感影响最大化模型

社交网络中影响最大化问题是寻找具有最大影响范围的节点。影响最大化的大部分求解算法仅仅依赖社交网络图。基于微博的转发关系树和微博内容的情感倾向性,以及用户的社交网络图,提出了一个能够刻画用户情感影响的情感影响最大化模型——情感影响分配模型(sentiment influence distribution,SID),证明了SID模型下的情感影响最大化问题是一个NP难问题,给出了一个具有精度保证的贪心算法。在真实的微博数据上的实验结果表明,SID模型能够有效地找出情感影响最大化的节点集,同时具有很高的扩展性。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

基于有重叠社区划分的社会网络影响最大化方法研究

社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。     

面向不确定图的k最近邻查询

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.     

一种高效的大规模网络k团挖掘算法

网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k－1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c²_k)和O(c_k)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。     

复杂网络的影响可控性

人们的行为受其他个体和连接彼此的社会网络的影响.研究基于影响网络的重要模型(DeGroot模型),在此模型中,社会网络可用一个加权的有向图表示,网络中的每个个体对某个共同的兴趣问题具有一个初始态度,由于网络中节点的相互影响而会逐步发生改变.提出一种框架用于分析复杂社会网络的影响可控性.结果表明,如果网络中存在持相反观点且对影响免疫的个体,群体对于命题的观点或态度可被固执的个体集合控制.通过分析网络完全影响可控或部分影响可控的条件,得到相应的可控准则.此外,提出控制影响网络的具体方法.由于网络的结构可控性已被广泛用于分析各种复杂网络,分析了网络的影响可控性与结构可控性的关系.     

异质网络中基于关键词属性的Truss社区搜索

社区搜索旨在信息网络中寻找与用户指定的查询节点高度相关的稠密连通子图,是社会网络分析的重要研究内容。现有的社区搜索方法大多是针对同质网络,但现实中的信息网络通常是包含多种节点类型和多种关系类型的属性异质网络。提出了异质网络中基于元路径P和元结构S的P-距离和S-距离及(k,d,P)-truss和(k,d,S)-truss社区模型以度量子图的结构内聚性,同时提出了关键词属性得分函数用于度量不同子图的关键词属性相关性,最后提出了搜索具有最高关键词属性得分的(k,d,P)-truss和(k,d,S)-truss的社区搜索算法。搜索算法能够找到同时具有结构内聚性和关键词属性相关性的个性化社区,并且支持限制查询节点与社区内任意节点的最大距离d来控制社区搜索的范围。在真实数据集上与相关的社区搜索算法进行了实验对比,结果证明了所提算法的有效性和可行性。     

有向传感器网络中基于概率感知模型的最小连通k覆盖集算法

无线传感器网络的基本问题之一是,网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测,这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的,该模型过于理想化,不能适用于复杂的应用环境,也不能应用于有向传感器网络中。针对上述局限,本文提出了有向传感器网络中基于概率感感知模型的最小连通k覆盖集问题（MCKS）,并指出这是NP难问题;设计了基于0-1整数规划和最小生成树的集中式近 BDA）,分别证明两种算法最终得到的是MCKS问题的可行解,并分析了算法的时间复杂度、性能比和通信复杂度。通过仿真实验并与ILP算法和BGA算法进行比较的结果表明： 在基于概率感知模型的条件下,IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖,并且激活节点数目较少,网络寿命延长。     

个体间相互影响的网络舆情演变模型

提出了一个社会网络中舆论形成的演化模型,模型考虑了网络中个体受其邻居影响的概率。假设个体A受到其他邻居影响的概率为α（A）,并且所有k度个体具有相同的受影响概率为α（k）,其中k是某个体邻居的个数。证明了如果概率α的分布满足对所有k满足α（k）=kp_kc,那么持某种舆论个体的人数比例是一个鞅,即数学期望是一个常数。本模型有助于衡量某给定社会网络中舆论传播的快慢程度。