精华内容
下载资源
问答
  • 社交网络影响力传播模型

    千次阅读 2020-02-12 19:47:05
    IC模型)是一种概率模型,当一个节点v被激活时,它会以概率p[v,w]对它未激活的出边邻居节点w尝试激活,这种尝试仅仅进行一次,而且这些尝试之间是互相独立的,即v对w的激活不会受到其他节点的影响。独立级联模型的...

    1.独立级联模型

    独立级联模型(Independent Cascade Mode,IC模型)是一种概率模型,当一个节点v被激活时,它会以概率p[v,w]对它未激活的出边邻居节点w尝试激活,这种尝试仅仅进行一次,而且这些尝试之间是互相独立的,即v对w的激活不会受到其他节点的影响。独立级联模型的信息传播过程为:

    (1)给定初始的活跃节点集合S,当在时刻t节点v被激活后,它就获得了一次对它的邻居节点w产生影响的机会,成功的概率为p[v,w],是随机赋予的系统参数,其自身独立不受其他节点的影响,该值越大,节点w越有可能被影响。

    (2)若w有多个邻居节点都是新近被激活的节点,那么这些节点将以任意顺序尝试激活节点w。如果节点v成功激活节点w,那么在t+1时刻,节点w转为活跃状态。

    (3)在t+1时刻,节点w将对其他节点产生影响,重复上述过程。

    需要注意的是,在上述传播过程中,在t时刻无论节点v是否能成功激活它的邻居节点,在以后的时刻,v本身虽然仍保持活跃状态,但它已经不再具备影响力,即在t时刻被激活的节点,已经尝试激活它自身的邻居节点后,在t+1时刻仍然处于活跃状态,但它本身已经不能再去激活其它任何节点,这一类节点称为无影响力的活跃节点。当网络中不存在有影响力的活跃节点时,传播过程结束。

    由于是概率模型,它的激活过程是不确定的,对于同一个网络,同样的种子节点进行激活得到的自后结果可能会差异较大。

    2.线性阈值模型

    线性阈值模型(Linear Threshold Model,LT模型)是一种价值积累模型,它对每个节点v都有一个激活阈值θ[v]∈[0,1]。线性阈值模型的信息传播过程如下:

    (1)给定集合中的任意节点v随机分配阈值θ[v]∈[0,1],该阈值表示这个节点受影响的难易程度,θ[v]越小,表示节点v越容易被影响,θ[v]越大,表示该节点v越难被影响。只有当节点v的新处于激活状态的邻居节点对它的影响力大于该阈值时,节点v才能被激活。

    (2)用权值b[w.v]表示节点v被它的邻居节点w的影响,∑w∈in(v) b[w,v]≤1表示节点v的处于活跃状态的邻居节点对它的影响力之和。这里in(v)是v的入边邻居节点集合。

    (3)给定初始的活跃节点集合A(网络中其余所有节点均处于非活跃状态),给网络中每个节点任意分配一个阈值,在t时刻,所有在t-1时刻处于活跃状态的节点仍保持活跃,并且当这一时刻节点v的邻居节点的影响力之和大于节点b的阈值时,节点v被激活,即节点v被激活的条件是v已激活的入边邻居对b的积累影响大于v的激活阈值,如下是所述:

    ∑w∈in(v) ,active(w)≠0 b[w,v]≥θ[v]

    (4)节点v被激活后,下一时刻将对它的邻居节点产生影响,重复上述过程。

    在LT传播模型中,当网络中已存在的所有活跃节点中任意活跃节点的影响力之和都不能激活他们的处于非活跃状态的邻居节点时,传播过程结束。

    它的激活过程时确定的,当我们对一个图用同样的种子节点来激活时,最后的传播范围是完全一样的。

    notes: 1.线性阈值模型中产生的影响会累计,而级联模型产生的影响不会累计。
    2.线性阈值模型结束时当无法继续激活非活跃节点,级联模型是当网络中没有有影响力的活跃节点

    转自:https://www.jianshu.com/p/b5c12b53ede4

    展开全文
  • 基于亲和传播的动态社会网络影响力扩散模型
  • 随着互联网和大数据的研究应用日益广泛,对社交网络影响力传播的研究成为数据挖掘和社交网络分析中的热点。从影响力传播模型、影响力传播学习和影响力传播优化3个方面总结了近些年计算机科学领域对影响力传播研究的...
  • 大数据企业基于大数据和信息化传播模型来引导企业的发展方向
  • 在考虑社会网络拓扑结构特征的基础上,提出了基于代数连通性的社会网络影响传播最大化模型模型以代数连通性为主要参量计算边的中心性,实现网络社区的快速划分,通过降维达到算法效率优化;模型挖掘社区内影响力大...
  • 依据新浪微博的实际数据,采用基于在线社交网络的动态消息传播模型仿真消息传播,根据仿真结果对度、介数、紧密度和K-shell等中心性指标的传播影响力进行对比分析,同时计算不精确函数和Pearson相关系数。...
  • 影响力最大化问题已经成为社会网络中重要的研究内容,其影响力传播模型和求解算法是关键的核心问题。为了提高预测传播结果的准确度,引入传播过程中激活节点数量动态变化与节点间信任关系对IC模型进行改进,结合社会...
  • 针对现有社交网络研究未能充分考虑网络拓扑结构的现状,通过...最后通过在数据集上的试验,试验结果证明给出的拓扑模型能较好的模拟信息在网络传播过程,改进后的PageRank算法能较好的对节点影响力进行评估和排序。
  • 社交网络影响力最大化——线性阈值模型(LT模型)算法实现(Python实现) 1、环境配置 环境配置:Win7 Pycharm Anaconda2 该算法每个节点的阈值设为 0.5 2、LT传播模型算法实现 linear_threshold.py (L....

    目录

    1、环境配置

    2、LT传播模型算法实现

    3、LT传播模型算法测试

    4、测试文件Wiki-Vote.txt数据


    社交网络影响力最大化——线性阈值模型(LT模型)算法实现(Python实现)

    1、环境配置

    环境配置:Win7 Pycharm Anaconda2

    该算法每个节点的阈值设为 0.5

     

    2、LT传播模型算法实现

    linear_threshold.py (LT传播模型算法)

    # -*- coding: utf-8 -*-
    """
    Implement linear threshold models
    社交网络影响力最大化 传播模型——线性阈值(LT)模型算法实现
    """
    import copy
    import itertools
    import random
    import math
    import networkx as nx
    
    __all__ = ['linear_threshold']
    
    #-------------------------------------------------------------------------
    #  Some Famous Diffusion Models
    #-------------------------------------------------------------------------
    
    def linear_threshold(G, seeds, steps=0):           #LT线性阈值算法
      """
      Parameters
      ----------
      G : networkx graph                     #所有节点构成的图
          The number of nodes.
    
      seeds: list of nodes                   #子节点集
          The seed nodes of the graph
    
      steps: int                             #激活节点的层数(深度),当steps<=0时,返回子节点集能激活的所有节点
          The number of steps to diffuse
          When steps <= 0, the model diffuses until no more nodes
          can be activated
    
      Return
      ------
      layer_i_nodes : list of list of activated nodes
        layer_i_nodes[0]: the seeds                  #子节点集
        layer_i_nodes[k]: the nodes activated at the kth diffusion step   #该子节点集激活的节点集
    
      Notes
      -----
      1. Each node is supposed to have an attribute "threshold".  If not, the
         default value is given (0.5).    #每个节点有一个阈值,这里默认阈值为:0.5
      2. Each edge is supposed to have an attribute "influence".  If not, the
         default value is given (1/in_degree)  #每个边有一个权重值,这里默认为:1/入度
    
      References
      ----------
      [1] GranovetterMark. Threshold models of collective behavior.
          The American journal of sociology, 1978.
      """
    
      if type(G) == nx.MultiGraph or type(G) == nx.MultiDiGraph:
          raise Exception( \
              "linear_threshold() is not defined for graphs with multiedges.")
    
      # make sure the seeds are in the graph
      for s in seeds:
        if s not in G.nodes():
          raise Exception("seed", s, "is not in graph")
    
      # change to directed graph
      if not G.is_directed():
        DG = G.to_directed()
      else:
        DG = copy.deepcopy(G)        # copy.deepcopy 深拷贝 拷贝对象及其子对象
    
      # init thresholds
      for n in DG.nodes():
        if 'threshold' not in DG.node[n]:
          DG.node[n]['threshold'] = 0.5
        elif DG.node[n]['threshold'] > 1:
          raise Exception("node threshold:", DG.node[n]['threshold'], \
              "cannot be larger than 1")
    
      # init influences
      in_deg = DG.in_degree()       #获取所有节点的入度
      for e in DG.edges():
        if 'influence' not in DG[e[0]][e[1]]:
          DG[e[0]][e[1]]['influence'] = 1.0 / in_deg[e[1]]    #计算边的权重
        elif DG[e[0]][e[1]]['influence'] > 1:
          raise Exception("edge influence:", DG[e[0]][e[1]]['influence'], \
              "cannot be larger than 1")
    
      # perform diffusion
      A = copy.deepcopy(seeds)
      if steps <= 0:
        # perform diffusion until no more nodes can be activated
        return _diffuse_all(DG, A)
      # perform diffusion for at most "steps" rounds only
      return _diffuse_k_rounds(DG, A, steps)
    
    def _diffuse_all(G, A):
      layer_i_nodes = [ ]
      layer_i_nodes.append([i for i in A])
      while True:
        len_old = len(A)
        A, activated_nodes_of_this_round = _diffuse_one_round(G, A)
        layer_i_nodes.append(activated_nodes_of_this_round)
        if len(A) == len_old:
          break
      return layer_i_nodes
    
    def _diffuse_k_rounds(G, A, steps):
      layer_i_nodes = [ ]
      layer_i_nodes.append([i for i in A])
      while steps > 0 and len(A) < len(G):
        len_old = len(A)
        A, activated_nodes_of_this_round = _diffuse_one_round(G, A)
        layer_i_nodes.append(activated_nodes_of_this_round)
        if len(A) == len_old:
          break
        steps -= 1
      return layer_i_nodes
    
    def _diffuse_one_round(G, A):
      activated_nodes_of_this_round = set()
      for s in A:
        nbs = G.successors(s)
        for nb in nbs:
          if nb in A:
            continue
          active_nb = list(set(G.predecessors(nb)).intersection(set(A)))
          if _influence_sum(G, active_nb, nb) >= G.node[nb]['threshold']:
            activated_nodes_of_this_round.add(nb)
      A.extend(list(activated_nodes_of_this_round))
      return A, list(activated_nodes_of_this_round)
    
    def _influence_sum(G, froms, to):
      influence_sum = 0.0
      for f in froms:
        influence_sum += G[f][to]['influence']
      return influence_sum
    
    
    

    3、LT传播模型算法测试

    test_linear_threshold.py(LT模型算法测试)

    #!/usr/bin/env python
    # coding=UTF-8                 #支持中文字符需要添加  coding=UTF-8
    from nose.tools import *
    from networkx import *
    from linear_threshold import *
    import time
    """Test Diffusion Models
    ----------------------------
    """
    if __name__=='__main__':
        start=time.clock()
        datasets=[]
        f=open("Wiki-Vote.txt","r")        #读取文件数据(边的数据)
        data=f.read()
        rows=data.split('\n')
        for row in rows:
          split_row=row.split('\t')
          name=(int(split_row[0]),int(split_row[1]))
          datasets.append(name)            #将边的数据以元组的形式存放到列表中
    
        G=networkx.DiGraph()               #建立一个空的有向图G
        G.add_edges_from(datasets)         #向有向图G中添加边的数据列表
        layers=linear_threshold(G,[6],2)     #调用LT线性阈值算法,返回子节点集和该子节点集的最大激活节点集
        del layers[-1]
        length=0
        for i in range(len(layers)):
            length =length+len(layers[i])
        lengths=length-len(layers[0])       #获得子节点的激活节点的个数(长度)
        end=time.clock()
        #测试数据输出结果
        print(layers)  #[[25], [33, 3, 6, 8, 55, 80, 50, 19, 54, 23, 75, 28, 29, 30, 35]]
        print(lengths) #15
        print('Running time: %s Seconds'%(end-start))  #输出代码运行时间
    
    

    4、测试文件Wiki-Vote.txt数据

    注释:测试文件Wiki-Vote.txt数据如下(每组数据代表图的有向边)

    # FromNodeId ToNodeId

    30 1412

    30 3352

    30 5254

    30 5543

    30 7478

    3 28

    3 30

    3 39

    3 54

    3 108

    3 152

    3 178

    3 182

    3 214

    3 271

    3 286

    3 300

    3 348

    3 349

    3 371

    3 567

    3 581

    3 584

    3 586

    3 590

    3 604

    3 611

    3 8283

    25 3

    25 6

    25 8

    25 19

    25 23

    25 28

    25 29

    25 30

    25 33

    25 35

    25 50

    25 54

    25 55

    25 75

    25 80

    数据获取,交流学习资料共享欢迎入QQ群:955817470

     

     

     

     

     

     

     

    展开全文
  • Barbieri, N., Bonchi, F., & Manco, G. (2012, December). Topic-aware social influence propagation models. In Data Mining (ICDM), 2012 IEEE 12th International Conference on (pp....社交网络

    Barbieri, N., Bonchi, F., & Manco, G. (2012, December). Topic-aware social influence propagation models. In Data Mining (ICDM), 2012 IEEE 12th International Conference on (pp. 81-90). IEEE.
     
    社交网络传播模型的共同特征:

    1. 用户成为活跃用户的可能性随着他的邻居中活跃用户的数量单调增加。
    2. 影响过程遵循Progressive规则,即用户只可能从非活跃受影响变成活跃,而不可能由活跃变成非活跃。
    • Linear Threshold Model 线性阈值模型:是以接受者为中心的模型
    • Independent Cascade Model 独立级联模型:是以发射者为中心的模型


    考虑时间延迟的模型(Continuous Time Delay Model):在传统的IC,LT基础上引入连续时间延迟,也就是CTIC,CTLT。用于话题传播行为分析。

    目标问题:确定有影响力的用户(例如病毒式营销中)

    问题:离散对待的时间和大量参数(效率,可扩展行和过度拟合(过适,是指在调适一个统计模型时,使用过多参数。))

    观察:1)用户有不同的兴趣;2)物品有不同的特征;3)用户有可能喜欢相似的物品
    研究对象:物品特征,用户兴趣,社会影响

    本文贡献:

    1. TIC和TLT
    2. Expectation Maximization (EM) 估计TIC模型的参数
    3. AIR (Authoritativeness-Interest-Relevance) 用户权威和话题兴趣取代user-to-user influence,减少参数
    4. Generalized Expectation Maximization (GEM) 用来学习最大似然来估计AIR模型的参数
    5. 使传统的IC模型可预测所接受的特定物品
    6. 考虑物品特征
    7. 在之前的topic-wise social influence加入Viral Marketing (病毒式营销) & Influence Maximization方法


    σm(S) is monotone & submodular (子模函数,随着加入集合的元素越多,  F 函数值获得的受益越少(效用边际递减)。)

    Influence maximization

    TIC (Topic-aware Independent Cascade Model)
    TLT (Topic-aware Linear Threshold Model)

    1. learning parameters of TIC model using Expectation-Maximization method (Complete-Data Expectation Likelihood[14], or log-likelihood maximization)
    2. 加入新物品item

    AIR propagation model
    parameters:

    1. authoritativeness of a user in a topic
    2. interest of a user for a topic
    3. relevance of an item for a topic

    principle: general threshold model [2]
    用selection scaling factors来控制时间衰变对信息传播的影响

    Influence Maximization in AIR: 

    • Greedy
    • Top-k authorities


    存在的问题和可以改进的地方:

    1. 这篇文章只是一个网络,不是异构网络,可以考虑构成user,item,topic三个网络的异构网络
    2. 只考虑到影响,并没有考虑到同质(personal影响,不只是结构影响,有可能是节点的属性影响传播)和环境
    3. 权威模型并不代表真的有效,容易被影响的人才能决定网络中信息的传播
    4. 网络的update,这篇文章只有item的update,并未涉及user关系的update

    未来工作的难点:

    1. 加入点东西使得影响的人更多影响力更大(Influence Maximization)
    2. 改进模型使得计算速度更快

    重要参考文献:

    [2] Kempe, D., Kleinberg, J., & Tardos, É. (2003, August). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146). ACM.

    原文永久链接:http://blog.wangting.me/post/60235966532/icdm12-topic-aware-social-influence-propagation

    展开全文
  • 进一步,对影响力的动态性进行了深入研究,引入短记忆过程和惩罚机制,从而构建动态影响力下的网络舆论传播模型,进行了计算实验分析.结果表明:随着群体信任阈值的提高,观点分化程度降低.群体观点演化也受初始影响...
  • 微博用户的节点特征决定了其网络影响力。研究了微博转发网络中节点的度值特征和传播模型。首先通过区分信息流动方向构建了微博转发网络;其次分别讨论了出度—入度的均值和方差,明确二者的差异,并分析了考虑节点度...
  • 社交网络影响力最大化

    万次阅读 2018-03-23 22:26:36
    3、社交网络影响力最大化作用 4、传播模型 4.1独立级联模型(Independent Cascade Model)简称 IC 模型 4.2线性阈值模型(Linear Threshold Model)简称LT模型 社交网络影响力最大化(Influence Maximization) ...

    目录

    1、社交网络概述

    2、影响力最大化问题分类

    3、社交网络影响力最大化作用

    4、传播模型

    4.1独立级联模型(Independent Cascade Model)简称 IC 模型

    4.2线性阈值模型(Linear Threshold Model)简称LT模型


    社交网络影响力最大化(Influence Maximization)

    1、社交网络概述

    社交网络归根结底就是一个图G(V,E,P),V是节点集,E是边集,P是所有边的概率集。一个用户就是一个节点v,用户与用户之间的关系就是边e,每条边都有一条概率p,信息会在图上按照边的概率进行传播。

    2、影响力最大化问题分类

    影响力最大化问题主要分为两种:

    (1)是给定节点数k,选择出k个节点作为种子集使得种子集能影响的节点数最多;

    (2)是给定所要求产生的影响力,找到满足条件的最小节点集合

    3、社交网络影响力最大化作用

    影响力最大化的应用场景十分丰富,包括病毒营销,推荐系统,信息扩散,时间探测,专家发现,链接预测等。

    我拿病毒营销举个例子,比如某一公司想要推广自家商品,希望通过病毒式营销手段,先选择少部分人让其免费试用所需推广的商品,当选中的用户(种子节点)对商品满意时便要通过网络向自己的同事朋友推荐该商品,使得更多的人了解并最终购买该商品。应该如何找出这部分人来试用商品能够使得最终购买商品的人数最多就是公司所需要考虑的最核心的问题。

    4、传播模型

    最经典的两种模型分别是:独立级联(IC)模型线性阈值(LT)模型

    4.1独立级联模型(Independent Cascade Model)简称 IC 模型

    它是一种概率型的传播模型。独立级联模型的基本原理描述如下:

    在社交网络G=(V,E)中,点集V中的节点具有两种状态一种是激活状态,一种是待激活状态,初始状态下,处于激活状态的节点会以一定的概率将与其相连的处于待激活状态下的节点激活。

    独立级联模型的影响力传播过程如下:

    (1) 在初始状态下,即 t=0 时,有且仅有种子集合 S 中的节点全部被设置为激活状态。

    (2) 当 t=k 时,所有在 t=k-1 时由待激活状态转变为激活状态态的全部节点,以一定的概率去尝试影响它们所有处于待激活态的邻居节点。例如点 i 在 t=k-1 时被激活,则 t=k 时,如果点 i 的邻居节点 j 仍处于待激活态,则点 i 以概率pij去尝试激活点 j。无论激活行为是否成功,在下一时刻,i 节点都将不再具备激活其他节点的能力。

    (3) 当某时刻整个网络中所剩余的具备激活其他节点能力的节点数为 0 时,传播过程结束

    4.2线性阈值模型(Linear Threshold Model)简称LT模型

          在线性阈值模型下,每个节点v包含从间隔[0,1]中随机均匀选择的激活阈值θv。 此外,LT规定所有进入边缘权重的总和最多为1,其它的进入节点对它的影响是累加的,当影响超过阈值时,该节点被激活。

    社交网络中的节点都有激活和待激活两种状态,每个节点由系统随机分配一个

     

    Python实现线性阈值模型算法下载:https://download.csdn.net/download/asialee_bird/10427607

     

    其他参考资料:

    博客学习:python复杂网络分析库NetworkXhttps://www.cnblogs.com/kaituorensheng/p/5423131.html

    学习复杂网络分析库NetworkX是实现社交网络影响最大化算法的基础

    NetWorkx学习:https://networkx.github.io/documentation/stable/reference/algorithms/clique.html#

     

    交流学习资料共享欢迎入QQ群:955817470

     

     

     

     

     

     

     

     

    展开全文
  • 本文首先介绍社交网络影响力最大化问题的相关理论知识,并重点研究了俩种影响力传播模型:独立级联模型(ICM),线性阈值模型(LTM)。最后基于典型的影响力最大化算法:贪心算法,提出一种改进的算法。
  • 1 影响力最大化问题在IC和LT模型上NP难。 在LT模型上,将最大覆盖问题规约到影响力最大化问题。 在IC模型上,将节点覆盖问题规约到影响力最大化问题。 2 利用次模函数可以得到1-1/e的近似比。 公式推导利用次...
  • 在移动社会网络中挖掘出有影响力的top-k节点, 对于移动运营商作出新产品或服务战略营销决策至关重要。针对移动社会网络的特点, 提出一种充分考虑移动社会网络特点的信息传播模型以及基于该模型的top-k节点挖掘算法。...
  • 分析了网络舆情的传播规律及其特点,利用系统动力学分析了网络舆论生态传播系统的驱动因素,通过因果回路图对因素之间的关系进行定性分析,并建立网络舆情驱动力模型。最后,对该模型进行仿真分析,以期提出积极管理...
  • 社交网络影响力最大化基础知识总结 一、影响力最大化定义 ...给定:社会网络图G=(V,E,W),设定的影响力传播模型,以及一个正整数K; 目标:从网络图G中选取初始活跃节点集合S,使得σ(S); 约束:S⊂V且|S|=K。...
  • 在社交网络上的信息传播的研究中,设定一个传播概率,运用各种传播模型来模拟信息传播过程,是最常见的一种方式,然而人为设定的传播概率对传播过程有很大影响。根据复杂网络的相关研究,计算信息源节点的影响力,并...
  • 然后提出了一个通过预测用户信息传播能力大小来分析和度量用户影响力的SRank用户影响力模型。在同样的数据集下相对于PageRank及其改进算法,SRank用户影响力模型获得了更好的影响力预测结果。基于大规模数据的实验...
  • 社交网络影响力最大化——贪心算法实现(Python实现) 1、环境配置 环境: Win7 Pycharm Anaconda2 该算法每个节点的阈值设为 0.5 2、LT传播模型算法实现 linear_threshold_clime.py(LT传播模型算法) #...
  • 社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高;...
  • 提出了社交网络意见领袖的胜任力模型模型中包括社交网络意见领袖所应具有的信息生产、信息传播以及信息影响3大能力要素及各个显性和隐性行为指标。根据胜任力模型,将社交网络用户划分为普通大众、活跃分子、主题...
  • 在一个在线社交网络中选择一组k个用户,即选出具有最大影响力传播的种子集,然后通过信息传播中的种子集来影响用户的预期数量最大。 2.1. 定义:扩散模型和影响扩散 给定社交图 G=(V,E)G = (V,E)G=(V,E),一个用户集...
  • 社会网络中的影响力最大化问题

    千次阅读 2017-09-22 21:28:43
    1 影响力传播模型 如果某个结点的相邻结点状态为激活的个数越多,则这个结点被激活的概率越大。这个激活过程不可逆,一个结点可以由不活跃状态转变为活跃状态,但是不能从活跃状态转变为活跃状态。影响力最大化问题...
  • 为研究用户传播能力差异性对垃圾信息传播影响,根据仓室建模思想,将传播网络中的人群划分为<i>I(ignorant)、<i>W(weakly spreader)、<i>S(strongly spreader)、<i>R(removal)四个仓室并提出状态转换规则...

空空如也

空空如也

1 2 3 4 5 6
收藏数 108
精华内容 43
关键字:

网络影响力传播模型