社交网络_社交网络分析 - CSDN
精华内容
参与话题
  • 一文读懂社交网络分析(附应用、前沿、学习资源)学习笔记一、社交网络的结构特性与演化机理1、社交网络结构分析与建模1.1 统计特性1.2 网络特性1.3 网络模型2、虚拟社区以及发现技术2.1 定义2.2 社区发现算法评估...

    一文读懂社交网络分析(附应用、前沿、学习资源)学习笔记

    原文链接:http://mt.sohu.com/20171010/n516921964.shtml

    一、社交网络的结构特性与演化机理

    1、社交网络结构分析与建模

    1.1 统计特性

    社交网络模型许多概念来自于图论,因为社交网络模型本质上是一个由节点(人)和边(社交关系)组成的图。

    • 度(Degree):节点的度定义为与该节点相连的边的数目。在有向图中,所有指向某节点的边的数量叫作该节点的入度,所有从该节点出发指向别的节点的边的数量叫作该节点的出度。网络平均度反应了网络的疏密程度,而通过度分布则可以刻画不同节点的重要性

    • 网络密度(Density):网络密度可以用于刻画节点间相互连边的密集程度,定义为网络中实际存在边数与可容纳边数上限的比值,常用来测量社交网络中社交关系的密集程度及演化趋势

    • 聚类系数(Clustering Coefficient):用于描述网络中与同一节点相连的节点间也互为相邻节点的程度。其用于刻画社交网络中一个人朋友们之间也互相是朋友的概率,反应了社交网络中的聚集性。

    • 介数(Betweeness):为图中某节点承载整个图所有最短路径的数量,通常用来评价节点的重要程度,比如在连接不同社群之间的中介节点的介数相对于其他节点来说会非常大,也体现了其在社交网络信息传递中的重要程度

    1.2 网络特性

    • 小世界现象:小世界现象是指地理位置相距遥远的人可能具有较短的社会关系间隔。早在1967年,哈佛大学心理学教授 Stanley Milgram 通过一个信件投递实验,归纳并提出了“六度分割理论(Six Degrees of Separation)”, 即任意两个都可通过平均五个人熟人相关联起来。1998年,Duncan Watts 和 Steven Strogatz 在《自然》杂志上发表了里程碑式的文章《Collective Dynamics of “Small-World” Networks》,该文章正式提出了小世界网络的概念并建立了小世界模型。
        小世界现象在在线社交网络中得到了很好地验证,根据2011年 Facebook 数据分析小组的报告, Facebook 约7.2亿用户中任意两个用户间的平均路径长度仅为4.74,而这一指标在推特中为4.67。可以说,在五步之内,任何两个网络上的个体都可以互相连接。
    • 无标度特性:大多数真实的大规模社交网络都存在着大多数节点有少量边,少数节点有大量边的特点,其网络缺乏一个统一的衡量尺度而呈现出异质性,我们将这种节点度分布不存在有限衡量分布范围的性质称为无标度。无标度网络表现出来的度分布特征为幂律分布,这就是此类网络的无标度特性。

    1.3 网络模型

    • WS 模型:WS 模型即小世界模型,通过小世界模型生成的小世界网络是从规则网络向随机网络过渡的中间形态。
    • BA 模型:BA模型考虑到现实网络中节点的幂律分布特性,生成无标度网络。
    • 其他模型:森林火灾模型,Kronecker 模型,生产模型。

    2、虚拟社区以及发现技术

    2.1 定义

    虚拟社区基于子图局部性的定义:社区结构是复杂网络节点集合的若干子集,每个子集内部的节点之间的连接相对非常紧密,而不同子集节点之间的连边相对稀疏
    在社交网络中发现虚拟社区有助于理解网络拓扑结构特点,揭示复杂系统内在功能特性,理解社区内个体关系。为信息检索、信息推荐、信息传播控制和公共事件管控提供有力支撑。虚拟社区发现存在着许多经典的算法,这些算法用于挖掘不同规模的虚拟社区,算法在追求高精度的同时力求提高效率(降低时间复杂度)。

    2.2 社区发现算法评估指标

    • 模块度(Modularity):通过比较现有网络与基准网络在相同社区划分下的连接密度差来衡量网络社区的优劣。
    • NMI (Normalized Mutual
      Information):利用信息熵来衡量预测社区结构一直社区结构的差异,该值越大,则说明社区结构划分越好,最大值为1时,说明算法划分出的社区结构和一直社区结构一致,算法效果最好。
    • Rand Index:表示在两个划分中都属于同一社区或者都属于不同社区的节点对的数量的比值。
    • Jaccard Index:Jaccard 系数用来衡量样本之间的差异性,是经典的衡量指标。

    2.3社区静态发现算法

    • 模块度最优算法
      Mark Newman 提出了针对模块度的最大化的贪心算法FN。可参考文献:Newman,Mark EJ. “Fast algorithm for detecting community structure innetworks.” Physical review E 69.6 (2004): 066133.

    • 多目标优化算法
      Zhao, Yuxin, et al. “Acellular learning automata based algorithm for detecting community structure incomplex networks.” Neurocomputing 151 (2015): 1216-1226.
      Du, Jingfei, Jianyang Lai,and Chuan Shi. “Multi-Objective Optimization for Overlapping CommunityDetection.” International Conference on Advanced Data Mining andApplications. Springer, Berlin, Heidelberg, 2013.

    • 基于概率模型的算法
      Newman, Mark EJ, andElizabeth A. Leicht. “Mixture models and exploratory analysis innetworks.” Proceedings of the National Academy of Sciences104.23(2007): 9564-9569.
      Ren,Wei, et al. “Simple probabilistic algorithm for detecting communitystructure.” Physical Review E 79.3 (2009): 036111.

    • 信息编码算法
      Rosvall, Martin, and Carl T.Bergstrom. “Maps of random walks on complex networks reveal communitystructure.” Proceedings of the National Academy of Sciences 105.4(2008): 1118-1123.
      Kim, Youngdo, and HawoongJeong. “Map equation for link communities.” Physical Review E 84.2(2011): 026110.

    2.4 社区动态发现算法

    • 派系过滤算法
      Palla, Gergely, et al.“Uncovering the overlapping community structure of complex networks innature and society.” arXiv preprint physics/0506133(2005).
      Kumpula,Jussi M., et al. “Sequential algorithm for fast cliquepercolation.” Physical Review E 78.2 (2008): 026109.
    • 基于相似度的聚合算法
      Shen, Huawei, et al.“Detect overlapping and hierarchical community structure innetworks.” Physica A: Statistical Mechanics and its Applications388.8(2009): 1706-1712.
      Huang,Jianbin, et al. “Density-based shrinkage for revealing hierarchical andoverlapping community structure in networks.” Physica A:Statistical Mechanics and its Applications 390.11 (2011): 2160-2171.
    • 标签传播算法
      Raghavan, Usha Nandini, RékaAlbert, and Soundar Kumara. “Near linear time algorithm to detectcommunity structures in large-scale networks.” Physical review E 76.3(2007): 036106.
      Gregory, Steve. “Finding overlapping communitiesin networks by label propagation.” New Journal of Physics 12.10(2010): 103018.
    • 局部扩展优化算法
      Lancichinetti, Andrea, andSanto Fortunato. “Benchmarks for testing community detection algorithms ondirected and weighted graphs with overlapping communities.” PhysicalReview E 80.1 (2009): 016118.
      Lee,Conrad, et al. “Detecting highly overlapping community structure by greedyclique expansion.” arXiv preprint arXiv:1002.1827 (2010).

    3、虚拟社区演化分析

    在线社交网络中存在着大量显性或者隐性的虚拟社区结构,这些虚拟社区结构并不是永恒不变的,随着事件变化,社区结构也在不断演变。分析动态的虚拟社区结构演化有助于理解整个社交网络的演化过程,所以有着重要的研究价值。

    3.1 虚拟社区的涌现

    虚拟社区涌现即在社交网络中虚拟社区从无到有的过程,其最重要的特征是网络聚集现象。

    • 周期闭包:所谓周期闭包,是指网络节点倾向于和自己在网络中邻居的邻居建立连接关系而形成的结构,该机制是导致虚拟社区形成的主要因素。实验表明三元闭包的出现概率随着两个节点之间测地距离的增减呈指数递减。相反地,焦点闭包和测地距离无关,其生成原因是两个节点之间有共同的兴趣或参与共同的活动。
    • 偏好连接:在很多真实网络中,新增加的边并不是随机连接的,而是倾向于和具有较大度数的连接。

    3.2 虚拟社区的演化

    在线社交网络虚拟社区演化过程非常复杂,影响因素很多。如何挖掘虚拟社区演化中的关键性因素成为社交网络研究中一个重要而有挑战性的课题, 用户个体的累积效应、结构多样性和结构平衡性三个基本因素对虚拟社区演化都存在影响。

    3.3 演化虚拟社区的发现

    • 基于相邻时刻相似度直接比较的演化虚拟社区发现

    Hopcroft, John, et al.“Tracking evolving communities in large linked networks.” Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.
    Greene, Derek, Donal Doyle, and PadraigCunningham. “Tracking the evolution of communities in dynamic socialnetworks.” Advances in social networks analysis and mining (ASONAM), 2010international conference on. IEEE, 2010.

    • 基于演化聚类分析的演化虚拟社区发现

    Chakrabarti, Deepayan, Ravi Kumar,and Andrew Tomkins. “Evolutionary clustering.” Proceedings ofthe 12th ACM SIGKDD international conference on Knowledge discovery and datamining. ACM, 2006.
    Lin, Yu-Ru, et al.“Facetnet: a framework for analyzing communities and their evolutions indynamic networks.” Proceedings of the 17th international conference onWorld Wide Web. ACM, 2008.

    • 基于拉普拉斯动力学方法的演化虚拟社区发现

    Lambiotte, Renaud, J-C.Delvenne, and Mauricio Barahona. “Laplacian dynamics and multiscalemodular structure in networks.” arXiv preprint arXiv:0812.1770 (2008).
    基于派系过滤算法的演化虚拟社区发现
    Palla, Gergely, Albert-LaszloBarabasi, and Tamas Vicsek. “Quantifying social groupevolution.” Nature 446.arXiv: 0704.0744 (2007): 664.

    • 基于节点行为趋势分析的演化虚拟社区发现

    Hopcroft, John, et al.“Tracking evolving communities in large linked networks.” Proceedingsof the National Academy of Sciences 101.suppl 1 (2004): 5249-5253.

    二、社交网络群体行为形成与互动规律

    1、用户行为分析

    社交网络用户行为是用户对自身需求,社会影响和社交网络技术进行综合评估的基础上做出的使用社交网络服务的意愿,以及由此引起的各种使用活动的总和。用户行为是在线社交网络研究的重要内容。现有研究主要基于如下两种思路展开,一是将在线社交网络作为一种特定的信息技术,研究用户对在线社交网络技术的采纳行为、拒绝行为和用户忠诚;二是将在线社交网络视为提供各种服务和应用的平台,研究用户使用各种服务和应用所表现出的特征与规律

    1.1 用户采纳与忠诚

    在线社交网络用户采纳是指用户在对自身需求、社会影响和在线社交网络技术进行综合评估的基础上做出的使用在线社交网络服务的意愿或行为,在线社交网络再出现初期能否被尽可能多的用户采纳和试用对于其后续的扩散至关重要。目前已有多种理论被用于揭示在线社交网络用户采纳行为机理。其中,技术接受模型计划行为理论是研究者们应用最多的两种理论。
    在线社交网络用户忠诚是指用户在使用社交网络服务之后,能够继续保持使用的习惯。各种层出不穷的新型网络服务所带来的竞争压力让保持在线社交网络用户忠诚度愈发困难。目前为止,已经有多种理论被用于在线社交网络的用户忠诚研究。其中,期望确认理论心流体验理论受到较多研究者青睐。

    • 基于技术接受模型的在线社交网络用户采纳模型

    David Fred 提出技术接受模型是目前信息系统研究领域最经典的模型之一。对模型详细了解可参考:
    Davis, Fred D. “Perceived usefulness, perceived ease of use, and user acceptance of information technology.” MIS quarterly (1989): 319-340.
    在这里插入图片描述

    • 基于计划行为理论的在线社交网络用户采纳模型
      Icek Ajzen 提出的计划行为理论已经被广泛用于人类行为研究。对理论详细了解可参考:
      Ajzen, Icek. “From intentions to actions: A theory of planned behavior.” Action control. Springer Berlin Heidelberg, 1985. 11-39.
      在这里插入图片描述
    • 基于期望确认理论的在线社交网络用户忠诚模型
      由 Oliver 提出的期望确认理论是研究消费者满意度的基本理论。 Anol Bhattacherjee 再该理论的基础上结合信息系统的特点提出了信息系统持续使用的期望确认模型(ECM-ISC)。对模型详细了解可参考:
      Bhattacherjee, Anol. “Understanding information systems continuance: an expectation-confirmation model.” MIS quarterly (2001): 351-370.
        在这里插入图片描述
    • 基于心流体验理论的在线社交网络用户忠诚模型
      Mihaly Csikszentmihalyi等提出的心流体验理论是目前关于用户体验研究的重要理论。对理论详细了解可参考:Csikszentmihalyi, Mihaly. Beyond boredom and anxiety. Jossey-Bass, 2000.
      在这里插入图片描述

    1.2 用户个体使用行为

    -** 一般使用行为**:用户可以在社交网络上执行各种各样的行为,例如浏览,点击,分享,点赞,收藏等等。具体的分类可参考:Benevenuto F,Rodrigues T, Cha M, Almeida V. Characterizing User Behavior in Online Social Networks. New York, New York, USA: ACM; 2009:49-62.doi:10.1145/1644893.1644900.

    • 内容创建行为:用户在社交网络通过写博客微博,发帖评论等行为产生内容,对内容创建行为的研究主要研究创建内容的动机、创建内容时的主题选择偏好以及内容创建时的语言表述等。关于主题,可通过搜索引擎搜索 LDA 模型。
    • 内容消费行为:用户在社交网络中通过浏览,分享和评论来满足他们的社交需求,对社交网络内容的消费可分为主动消费和被动消费。被动消费即“浏览”,有研究表明,社交网络中高达92%的行为都是浏览行为。主动消费即社交搜索,例如搜索朋友的信息以及向社交圈内好友提问等等。

    用户群体互动行为

    • 群体互动关系选择:对群体互动关系的研究主要是识别用户之间的关系,通过制定不同的衡量指标,研究用户之间的关系强弱。
    • 群体互动的内容选择:社交网络中用户对内容选择与其社交关系密不可分。例如有研究表明两位维基百科编辑在互动前后产生的编辑内容的相似性有所不同。
    • 群体互动的时间规律:在线社交网络中人类行为的时间特征研究主要集中于分析行为发生的时间间隔分布。研究发现在线社交网络中用户行为时间间隔分布不同于传统的负指数分布,而是呈现幂律分布,即具有“长尾效应”。对群体互动时间规律的研究可以应用到公共管理和决策等场景中。

    2、社交网络情感分析

    随着互联网技术的迅速发展,网络已经成为人们获取信息,发表意见的主要途径,根据文本内容,我们可以将网络中的文本分为两种,一种是客观描述信息,主要针对事件、产品等进行客观描述,另一种是主观性信息,主要产生与用户对人物、事件、产品进行客观性描述;另一种是主观性信息,主要产生于用户对人物、事件、产品等的评价信息。主观性信息表达了人们的各种情感色彩和情感倾向,如“支持”、“反对”、“中立”等。
    情感分析,在此等同于意见挖掘,是针对主观性信息进行分析、处理和归纳过程。情感分析最初起源于自然语言处理领域,主要从语法语义规则方面对文本的情感倾向性进行研判。随着社交网络的兴起与发展,情感分析逐渐涉及多个研究领域,如文本挖掘、Web 数据挖掘等,并延伸至管理学及社会科学等学科,并在产品评论、舆情监控、信息预测等多个领域发挥着重要的作用。

    2.1 文本情感分析技术

    • 基于语义规则的情感分析技术:我们将一句话中的带有感情的形容词和副词提取出来构成一个情感词典,这些词语可以代表用户的某种倾向性。基于语义规则的分析技术是计算评价词和情感词典中已经标注倾向性词语的距离,从而达到情感分类的目的。其最经典的算法是SO-PMI 算法。
    • 基于监督学习的情感分析方法:基于监督学习的方法是首先通过人工标注文本的情感极性,然后将此作为训练集,通过机器学习的方法对目标文本进行情感分类。常用方法:朴素贝叶斯,支持向量机。
    • 基于话题模型的情感分析技术:有两个话题模型,PLSA (Probabilistic Latent Semantic Analysis)和LDA (Latent Dirichlet Allocation) 模型,网络上有大量的学习资料可供读者进一步了解。

    2.2 社交网络情感分析技术

    • 面向短文本的情感分析技术:社交网络产生大量的短文本,例如微博和新闻评论,论坛帖子等等,这些短文本不同于新闻报道,其语法不规则,充斥大量噪声,因此对短文本的分析非常重要。
    • 基于群体智能的情感分析技术:用户在社交网络中表达意见会受到其社交关系的影响,情感会沿着社交关系进行传播,因此可以通过研究社交用户之间的关系来提高情感分析的准确度。
    • 社交网络的垃圾意见挖掘技术:社交网络中的垃圾意见,包括水军与广告等信息,通过对垃圾意见的挖掘,能够有效区分有效信息和垃圾信息,从而提高社交网络使用体验。

    3. 个体影响力分析

    发现社交网络中的有影响力的个体是社交网络研究中非常重要的研究分支,而且其有着重要的应用价值。例如微博营销,谣言检测,舆情管理等等。

    3.1 基于网络结构的个体影响力计算

    基于社交网络的图结构特性,有几个指标用来衡量网络中节点的中心度,即节点的影响力。除了以下三种外还有 PageRank 中心度等度量方法。

    • 度中心度(Degree Centrality):度中心度是指与该节点直接相连的节点的数量。
    • 接近中心度 (Closeness Centrality):指某节点与网络中所有其他节点的最短距离之和。
    • 介数 (Betweenness Centrality):介数用来衡量某节点在社交网络中中介作用大小。网络中某两个节点所有最短路径的数量除以这些路径中经过 A节点路径的数量便是 A 节点的介数,也叫中间中心度。

    3.2 基于行为的个体影响力计算

    社交网络中用户的行为决定用户的影响力,以微博为例,用户主要表现的行为是评论、转发、回复、点赞、复制、阅读等等,基于这些行为特征构建多种网络关系图,可通过随机游走等方法发现网络中的影响力个体。

    3.3 基于话题的个体影响力计算

    在社交网络中用户在不同话题下的影响力不同,可以根据用户的关注网络和用户兴趣相似性来计算用户在每个话题上的影响力。

    4、群体聚集以及影响机制分析

    本部分主要介绍群体极化的概念。群体极化是指在群体决策的情境中,个体意见或决定往往会受到群体间的彼此讨论的影响,而产生一个群体性的结果。群体极化往往表现为群体内的个体不经过个人思考而同意大多数人的观点。群体极化是一个社会心理学概念,在社会学名著《乌合之众》中提到的大众心理状态就是群体极化的体现。
    ** 群体极化产生的条件可概括为四点:第一,必须有激发事件出现;第二,群体内的个人能看到前人的选择;第三,群体信息缺乏;第四,群体有一定的同质性**。
    在在线社交网络分析中,人们通过建立分析模型和仿真来研究在线社交网络中的群体极化现象。主要的分析模型有基于博弈论和委托—代理理论的从众行为模型,基于信息瀑的群体一致性模型和基于元胞自动机群决策和行为仿真。

    三、社交网络信息传播与演化机理

    1、在线社交网络信息检索

    信息检索(Information Retrieval) 是从大规模非结构化数据中获取信息的过程,例如搜索引擎就是典型的信息检索技术的应用。在线社交网络数据结构有其特殊性,以微博的“话题”(#话题名称#)为例,这种新型的信息组织方式是传统信息检索研究没有涉及的,所以对社交网络信息的检索成为了一门研究课题。

    1.1 社交网络内容搜索

    内容搜索是指给定查询,从大量信息中返回相关信息的过程。例如在微博上搜索相关热点事件名称,能够返回关于热点事件的微博。内容搜索是信息检索最经典的应用形式。经典的信息检索模型有向量空间模型(VSM),概率模型及 BM25检索公式,基于统计建模检索模型及查询拟然模型,基于统计语言建模的检索模型等。
    针对微博的内容检索建模,目前有两种主要的方法:

    • 时间先验方法:时间先验是由于语料库中的文档具有不同的重要性,考虑语料库背景定义不同的计算公式,再将计算结果用于检索模型以期得到更好的检索效果的一种检索方法。目前考虑时间信息计算文档先验的研究工作可分为两种:一种定义文档的时间变化关系;另一种为修改PageRank 的方法,在其中加入时间关系。具体细节可参考:
      Li, Xiaoyan, and W. Bruce Croft. “Time-based language models.” Proceedings of the twelfth international conference on Information and knowledge management. ACM, 2003.
      Yu, Philip S., Xin Li, and Bing Liu. “On the temporal dimension of search.” Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters. ACM, 2004.
    • 多特征组合的方法:多特征组合方法是通过组合多个微博特性来检索微博内容。下面的参考文献中提到的微博特性有:微博个数,关注数,粉丝数,微博长度,微博是否含有外链。具体细节可参考:
      Li, Nagmoti, Rinkesh, Ankur Teredesai, and Martine De Cock. “Ranking approaches for microblog search.” Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on. Vol. 1. IEEE, 2010.

    1.2 社交网络内容分类

    面向文本的分类称为文本分类。分类包括训练和测试两阶段,简单地说,训练是根据已标注类别的语料来学习分类规则或规律的过程。而测试是将已训练好的分类器用于新文本的过程。不管是训练还是测试,都需要将分类对象进行特征表示,然后利用分类算法进行学习或者分类。以下社交网络中内容主题分类的相关参考文献,读者可自行查阅。
      Liu, Zitao, et al. “Short text feature selection for micro-blog mining.” Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on. IEEE, 2010.
      Yuan, Quan, Gao Cong, and Nadia Magnenat Thalmann. “Enhancing naive bayes with various smoothing methods for short text classification.” Proceedings of the 21st International Conference on World Wide Web. ACM, 2012.
      Ling, Xiao, et al. “Can chinese web pages be classified with english data source?.” Proceedings of the 17th international conference on World Wide Web. ACM, 2008.
      Zhang, Dan, et al. “Transfer Latent Semantic Learning: Microblog Mining with Less Supervision.” AAAI. 2011.

    1.3 社交网络推荐

    • 协同过滤推荐:传统的协同过滤根据用户(user)和物品(item)信息构建矩阵,根本的原则是相似用户的选择也相似,例如 a 和 b 都喜欢m,其中 a 还喜欢 n,那么 b 也有可能喜欢m。在社会化协同过滤推荐中,我们可以利用用户之间的社交关系,弥补协同过滤矩阵中缺失的内容,从而使协同过滤的结果更加精准。
    • 基于模型的推荐
      邻居模型:Ma, Hao, et al. “Sorec: social recommendation using probabilistic matrix factorization.” Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008.
      矩阵分解模型:Funk, Simon. “Netflix update: Try this at home.” (2006).
      融入社交网络信息:Jamali, Mohsen, and Martin Ester. “A matrix factorization technique with trust propagation for recommendation in social networks.” Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010.

    2、社交网络信息传播规律

    信息传播是人们通过符号、信号、传递、接收与反馈信息的活动,是人们彼此交换意见、思想、情感,已达到互相了解和影响的过程。社交网络信息传播是指以社交网络为媒介进行信息传播的过程。研究社交网络信息传播的规律,有助于我们加深对社交系统的认识,理解社交现象。也有助于模式发现,大影响力节点识别和个性化推荐。下面主要介绍几种社交网络信息传播模型。

    2.1 基于网络结构的传播模型

    线性阈值模型( Linear Threshold)
      Granovetter, Mark. “Threshold models of collective behavior.” American journal of sociology 83.6 (1978): 1420-1443.
    独立级联模型( Independent Cascade)
      Goldenberg, Jacob, Barak Libai, and Eitan Muller. “Talk of the network: A complex systems look at the underlying process of word-of-mouth.” Marketing letters 12.3 (2001): 211-223.

    2.2 基于群体状态的传播模型

    传染病模型(SI, SIS, SIR), 传染病模型是经典的信息传播模型,网上有丰富的参考资料。
    线性影响力模型( Linear Influence Model)
      Yang, Jaewon, and Jure Leskovec. “Modeling information diffusion in implicit networks.” Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

    2.3 基于信息特征的传播模型

    在线社交网络中的信息承载着用户网上活动的所有记录,在信息传播分析时起着不可或缺的重要作用。信息本身也具有一些特性,例如时效性,主体多样性,多源触发,信息合作与竞争等。依据这些特征,可建立不同的模型。
    对社交网络信息传播规律的研究还包括热度预测和信息溯源。
    Myers, Seth A., Chenguang Zhu, and Jure Leskovec. “Information diffusion and external influence in networks.” Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.
    Beutel, Alex, et al. “Interacting viruses in networks: can both survive?.” Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012.

    3、话题发现与演化

    在话题发现和演化的大部分研究中,话题是指一个引起关注的事件或活动,及其所有相关事件和活动。其中,事件或者活动是指在一个特定的时间和地点,发生的一些事情。社交网络语料库中的数据和传统话题发现语料库的数据区别较大,所以我们必须使用新的方法或对传统方法进行改进来适应社交网络数据特点。
    一般社交网络例如 Twitter 的数据有以下特点:数据规模大、内容简短、噪声多、数据特征丰富等。下面介绍几种主要的话题发现和演化模型。

    3.1 基于主题模型的话题发现

    最具有代表性的主题发现模型——LDA
    Blei, David M., Andrew Y. Ng, and Michael I. Jordan. “Latent dirichlet allocation.” Journal of machine Learning research 3.Jan (2003): 993-1022.

    3.2 基于向量空间模型的话题发现

    Salton, Gerard, Anita Wong, and Chung-Shu Yang. “A vector space model for automatic indexing.” Communications of the ACM 18.11 (1975): 613-620.
    Becker, Hila, Mor Naaman, and Luis Gravano. “Beyond Trending Topics: Real-World Event Identification on Twitter.” ICWSM 11.2011 (2011): 438-441.

    3.3 基于词项关系图的话题发现

    词项共现是自然语言处理技术在信息检索中的成功应用之一。它的核心思想是词项之间的共现频率在某种程度上反映了词项的语义关联。最初学者们利用词项共现来计算文档的相似性,随后学者们利用该方法来完成话题词提取,话题句提取和摘要生成任务。
      Sayyadi, Hassan, Matthew Hurst, and Alexey Maykov. “Event detection and tracking in social streams.” Icwsm. 2009.

    3.4 基于主题模型的话题演化

    Yin, Zhijun, et al. “LPTA: A probabilistic model for latent periodic topic analysis.” Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.
    Wang, Xiaolong, Chengxiang Zhai, and Dan Roth. “Understanding evolution of research themes: a probabilistic generative model for citations.” Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.

    3.5 基于相邻时间片关联的话题演化

    Lin, Cindy Xide, et al. “The joint inference of topic diffusion and evolution in social communities.” Data Mining (ICDM), 2011 IEEE 11th International Conference on. IEEE, 2011.
    Saha, Ankan, and Vikas Sindhwani. “Learning evolving and emerging topics in social media: a dynamic nmf approach with temporal regularization.” Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

    4、影响力最大化

    影响力最大化是在社交网络中选定信息初始传播用户,使得信息的传播范围能达到最大,即影响力最大。影响力最大化算法的目的就是找出一定数量的用户作为影响力传播的初始节点。对影响力最大化的问题的建模是基于社交网络信息传播模型的。其中最经典的模型是线性阈值和独立级联模型。
    影响力最大化算法被证明为 NP-hard问题,下面主要介绍两种典型的影响力最大化算法。

    4.1 贪心算法

    贪心算法从单个节点开始,计算每选一个新节点作为初始节点对每个节点带来的边际收益,取能造成边际收益最大的点加入初始节点集合。贪心算法的缺点是计算时间成本较大,但是计算精度较高。
      Kempe, David, Jon Kleinberg, and Éva Tardos. “Maximizing the spread of influence through a social network.” Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2003.
      Chen, Wei, Yajun Wang, and Siyu Yang. “Efficient influence maximization in social networks.” Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

    4.2 启发式算法

    不同于贪心算法选择任何一个点作为初始节点开始计算,启发式算法先通过一定策略选取一定数量的初始节点,然后计算其影响力传播。其优点是速度快,缺点是精度低。
      Chen, Wei, Yajun Wang, and Siyu Yang. “Efficient influence maximization in social networks.” Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.
      Chen, Wei, Yifei Yuan, and Li Zhang. “Scalable influence maximization in social networks under the linear threshold model.” Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.

    四、社交网络分析的应用

    1、社交推荐

    社交推荐顾名思义是利用社交网络或者结合社交行为的推荐,具体表现为推荐 QQ 好友,微博根据好友关系推荐内容等。在线推荐系统最早被亚马逊用来推荐商品,如今,推荐系统在互联网已无处不在,目前大热的概念“流量分发是互联网第一入口”,支撑这个概念有两点核心,其一是内容,另外就是推荐,今日头条在短短几年间的迅速崛起便是最好的证明。
      根据推荐系统推荐原理,社交推荐可定义为一种“协同过滤”推荐,即不依赖于用户的个人行为,而是结合用户的好友关系进行推荐。对于互联网上的每一个用户,通过其社交账户能很快定义这个用户众多特点,再加之社交网络用户数之多,使得利用社交关系的推荐近些年备受关注。
      笔者所了解到的研究有,根据不同社交网络之间进行信息信息匹配进而进行推荐,有根据社交关系解决新注册用户的冷启动问题等。如果想了解这方面更多信息还可以关注推荐系统领域顶级会议 ACM RecSys。

    2、舆情分析

    舆情分析在互联网出现之前就被广泛应用在政府公共管理,商业竞争情报搜集等领域。在社交媒体出现之前,舆情分析主要是线下的报纸,还有线上门户网站的新闻稿件,这些信息的特点是相对专业准确,而且易于分析和管理;但随着社交媒体出现,舆情事件第一策源地已经不是人民日报新华社这样的大媒体,而是某一个名不见经传的微博用户,一个个人微信公众号。他们的特点是信息非常新鲜,缺点是真实度较低且传播十分迅速,难以控制。所以在社交网络下的舆情分析是一门新的学问。

    3、隐私保护

    在隐私保护领域,一方面要设计足够安全的机制,技术层面的,法律层面的,在保护个人隐私的前提下最大化商业利益和用户的体验。
    举一个大家比较熟悉的例子,即许多网站注册账户的时候使用微信、支付宝账户验证,即免去了大家填写个人信息的烦恼,又保护了大家的隐私。同理,蚂蚁金服提供的芝麻信用功能也有隐私保护的功能。

    4、用户画像

    用户画像,这是个营销术语,即通过研究用户的资料和行为,将其划分为不同的类型,进而采取不同的营销策略。传统的用户画像最常用的手段就是调查问卷,订阅过杂志和报纸的读者都知道,会有各种各样的有奖问卷,一方面用来获得对于产品的反馈,另一方面就是对你进行画像,这些画像资料甚至广泛在黑市流通,这就是你为什么有时候会接到莫名其妙的电话的原因(又扯到了隐私保护问题)。

    5、谣言检测

    传统辟谣方法无非是进行试试检验,用证据说话,随着现在机器学习技术的迅速发展,我们也可以通过信息传播的轨迹,信息内容等维度自动判断消息是否属于谣言,而且判断地越迅速,对于舆情管理的意义就越大。同理,这种技术也被应用在社交网络有害信息识别。

    6、可视化

    五、社交网络前沿研究

    搜集了几篇近两年来在社交网络顶级会议上比较受关注的文章,将文章的摘要翻译并陈列,以供各位读者参考。

    1. Negative Link Prediction in Social Media

    Tang, Jiliang, et al. “Negative link prediction in social media.” Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. ACM, 2015
      近年来,符号网络(signed network)越来越受到关注。对于符号网络的研究表明,负关系(negative link)对分析过程有帮助。由于许多网络中用户无法指定这种负关系,这是其被有效利用的主要障碍。话句话说,负关系的重要性与其在真实数据集之间的应用存在着差距。因此,我们自然而然会探讨是否能通过公开的社交网络数据自动预测用户的负关系。在本文中,我们研究了在社交媒体中仅仅用正关系和内容为中心的交互行为(content-centric interactions)来预测负关系的问题。我们对负关系做了一些列观测并且提出了一个原则性框架 NeLP,该框架可以利用正关系和以内容为中心的交互来预测负关系。我们对在现实社交网络的实验结果表明,NeLP框架可以准确地预测具有正关系和以内容为中心的交互关系的负关系。 我们的详细实验还说明了各种因素对NeLP框架有效性的重要性。

    2. Twitter Sentiment Analysis with Deep Convolutional Neural Networks

    Severyn, Aliaksei, and Alessandro Moschitti. “Twitter sentiment analysis with deep convolutional neural networks.” Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2015
      本文介绍了我们用于推特舆情分析的深度学习系统。我们工作主要的贡献是提出了一个初始化卷积神经网络参数权重的模型,这对于准确训练模型至关重要,同时避免增加新的特征。简而言之,我们用无监督神经语言模型来训练初始的词嵌入(initial word embeddings),这个词嵌入将被通过我们的基于远程监督语料库(distant supervised corpus)的深度学习模型进一步调整。在最后阶段,预先训练的参数将被用于初始化我们的模型,然后我们通过由Semeval-2015组织的Twitter情绪分析官方系统评价竞赛最近提供的监督训练集对后者进行培训。我们的方法得到的结果和参与竞赛的系统的结果之间的比较表明,我们的模型可以分别排在短语级别子任务A(11个团队)和消息级子任务B(40个团队)前两位。这证明了我们解决方案的实际价值。

    3. Social Recommendation with Strong and Weak Ties

    Wang, Xin, et al. “Social Recommendation with Strong and Weak Ties.” Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 2016
      随着在线社交网络的爆炸式增长,现在人们普遍了解,社会信息对推荐系统非常有帮助。社会推荐方法能够应对关键的冷启动问题,从而可以大大提高预测精度。主要的原因是,基于信任和影响,人们对其朋友购买过的产品表现出更多的兴趣。尽管在社交推荐领域已经有大量工作,但是很少有人关注社交强关系和弱关系这两个重要的社会学概念之间的区别。在这篇文章中,我们使用邻域重叠来逼近关系强度,并扩展受欢迎的贝叶斯个性化排名(BPR)模型并将其用于区别强弱关系。我们提出了一种基于 EM (EM-based)的算法,它可以根据最优推荐准确度(optimal recommendation accuracy)对强弱关系进行分类并学习所有用户和所有商品的潜在特征向量(latent feature vectors)。我们对四个现实世界数据集进行广泛的实验,并证明我们提出的方法在各种精度指标中显著优于目前最好的成对排名(pairwise ranking)方法。

    4. Online Actions with Offline Impact: How Online Social Networks Influence Online and Offline User Behavior

    Althoff, Tim, P. Jindal, and J. Leskovec. “Online Actions with Offline Impact: How Online Social Networks Influence Online and Offline User Behavior.” Tenth ACM International Conference on Web Search and Data Mining ACM, 2016:537-546
      如今许多应用软件都广泛地利用了社交网络功能并允许用户互相连接、互相关注、分享内容和评价动态。尽管这些功能已经被广泛应用,对于用户在线时和离线后参与还是保留的行为却很少有人理解。本文中,我们通过一个运动记录 APP研究了社交网络是如何影响用户线下行为的。
      我们分析了600万用户五年间的七亿九千一百万条线上和线下活动记录,结果表明社交网络对用户线上和线下的行为有着巨大的影响。具体来讲,我们提出了社交网络影响用户行为的因果关系。我们发现新社交关系的建立能将用户在 APP 中的活跃度提高30%,用户保留率提高17%,线下活跃率提高7%(大约每天多走400步)。通过开展自然实验,我们将新社交关系对用户的影响和用户因为对 APP 的兴趣而走更多步数作了区分。
      我们发现社交影响占所有对用户行为影响因素的55%,剩下的45%可以用用户对 APP 本身的兴趣来解释。此外我们还发现一连串的个人用户之间的社交关系建立对每日步数的增加有显著影响,用户之间每增加一条边都对会减弱这种影响,并且这些变化是基于边属性和用户自己的资料属性。最后我们用这些现象设计了一个模型,模型用来判断哪些用户最容易被新建立的社交网络关系影响。

    Intertwined Viral Marketing in Social Networks

    Zhang, Jiawei, et al. “Intertwined viral marketing in social networks.” Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on. IEEE, 2016
      传统的病毒式营销问题旨在为一个单一产品选择一个种子用户的子集,以最大限度地提高其在社交网络中的知名度。而然在实际情况下,许多产品可以同时在社交网络中进行推广。从产品层面来看,这些产品之间的关系是互相缠绕的,举个例子,就是竞争、互补且独立的关系。
      在这篇文章中,我们将研究“纠缠影响力最大化”问题,它是基于一个目标产品需要在社交网络上进行宣传,而同时有多个竞争/互补/独立的产品在推广这样的场景。纠缠影响力最大化是一个非常具有挑战性的问题,首先是因为很少有模型能模拟多种产品同时宣传时的信息扩散形式;第二是对于目标产品最优种子集的选择可能很大程度上取决于其它产品的营销策略。为了解决此问题,我们提出了一种统一贪心算法框架(interTwined Influence EstimatoR, TIER),在四种不同类型现实社交网络数据集的实验表明TIER 优于所有的比较方法,在解决纠缠影响力最大化问题上有着显著优势。

    Who to Invite Next? Predicting Invitees ofSocial Groups

    Yu Han, and Jie Tang. "Who to Invite Next?Predicting Invitees of Social Groups " Proceedings of theTwenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17).2017.
      WhatsApp、Snapchat 和微信等社交即时通讯工具很大程度上改变了人们工作生活和交流的方式,也受到了多个领域例如计算机科学、心理学、社会学和物理学的关注。在社交即时消息工具中,社交群组在多用户交流中扮演着重要的角色。一个有趣的问题是,社交群组动态演变的机制是什么?更具体来说,在一个群组中,谁将会被邀请加入?这篇文章中,我们研究社交群组潜在加入者这样一个新颖的问题。我们采用微信这个中国最大的社交软件作为实验数据的来源。我们提出了一个概率图模型用来计算影响用户被邀请加入群组概率的因子。我们的实验预测结果表明我们的模型相比目前的其他模型有显著的提高。

    7. The Co-Evolution Model for Social NetworkEvolving and Opinion Migration

    Gu,Yupeng, Yizhou Sun, and Jianxi Gao. “The Co-Evolution Model for SocialNetwork Evolving and Opinion Migration.” Proceedings of the 23rd ACMSIGKDD International Conference on Knowledge Discovery and Data Mining.ACM, 2017.
      几乎所有的真实社交网络都是动态且随着时间演化的。新的链路的形成和旧的链路的消失很大程度上取决于社交网络用户的同质性。同时,一些社交网络用户的隐性性质例如用户的观点也随着时间而变化。其中一部分原因是用户从社交网络中接收到影响力,这些改变进而会影响社交网络的结构。社交网络的演化和节点性质的迁移通常被认为是两个独立正交的问题。
      在这篇文章中,我们提出一种协演化模型,通过对两种现象的建模形成闭环。模型有两个主要部分:(1)一个已知节点性质的网络生成模型;(2)一个已知社交网络结构的节点性质迁移模型。
      通过模拟发现我们的模型有一些不错的特性:(1)它可以模拟一个大范围现象,例如观点的收敛和基于社群的观点差异;(2)它可以通过一系列因子例如社交影响力范围,意见领袖,噪声等级来控制网络的演化。
      最后,我们模型的有效性通过在对议会立法议案支持者的预测中得到了验证,并且我们的模型优于一些目前的方法。

    展开全文
  • 社交网络分析初步学习1.md

    千次阅读 2018-10-09 09:46:09
    社交网络分析初步学习1 理论(用户分类)和应用两个方向 【关键词】社交网络,拓扑结构,网络群体,信息传播 1 什么是社交网络(在线) 1.1 定义 社交网络在维基百科的定义是:”由许多节点构成的一种社会结构",...

    社交网络分析初步学习1

    理论(用户分类)和应用两个方向

    【关键词】社交网络,拓扑结构,网络群体,信息传播

    1 什么是社交网络(在线)

    1.1 定义

    社交网络在维基百科的定义是:”由许多节点构成的一种社会结构",节点通常是指个人或组织,而社交网络代表着各种社会关系

    1.2 分类

    1. 即时消息类应用,即一种提供在线实时通信的平台,如MSN、QQ、飞信、微信等;
    2. 在线社交类应用,即一种提供在线社交关系的平台,如Facebook、Google、人人网等;
    3. 微博类应用,即一种提供双向发布短信息的平台,如Twitter、新浪微博、腾讯微博等;
    4. 共享空间等其他类应用,即其他可以相互沟通但结合不紧密的Web2.0 应用,如论坛、博客、视频分享、社会书签、在线购物等。

    1.3 影响

    基于互联网的社交网络已经成为了人类社会中社会关系维系和信息传播的重要渠道和载体,对国家安全和社会发展产生着深远的影响.虚拟的社交网络和真实社会的交融互动对社会的直接影响巨大,所形成的谣言、暴力、欺诈、色情等不良舆论会直接影响国家安全与社会发展。

    2 社交网络分析研究的核心问题

    2.1 三个组成要素

    在线社交网络是一种在信息网络上由社会个体集合个体(也称为节点)之间的连接关系构成的社会性结构,包含关系结构(载体)、**网络群体(主体)网络信息及其传播(客体)**3 个要素。

    1. 社交网络中的“关系结构”为网络群体互动行为提供了底层平台,是社交网络的载体。社交网络的关系结构是社会个体成员之间通过社会关系结成的网络系统;
    2. “网络群体”直接推动网络信息传播,并反过来影响关系结构,是社交网络的主体。网络社会群体行为是指网络个体就某个事件某个虚拟空间聚合或集中,相互影响、作用、依赖,有目的性地以类似方式进行的行为;
    3. “网络信息及其传播“是社交网络的出发点和归宿,也是群体行为的诱因和效果,同样影响关系结构的变化,是社交网络的客体。基于社交网络的信息传播是指社交网络中的个体与个体之间、个体与群体之间、群体与群体之间的信息传递。

    2.2 三个研究对象

    1. 社交网络本身的结构特性
    2. 社交网络中的群体及其行为
    3. 社交网络中的信息及其传播

    2.3 三类研究问题(结构、群体、信息)

    (1)在线社交网络的结构特性与演化机理。

    1. 社交网络的表达方式
    2. 什么样的表示方法既能反映社交网络的本质,又能支持计算和分析?
    3. 什么样的计算方法能够准确刻画社交网络结构的演化?

    (2)在线社交网络群体行为形成与互动规律。

    1. 在社交网络中如何刻画群体的存在及其形成方式?
    2. 群体间的交互影响如何进行表示与度量
    3. 群体间的交互过程对群体的演变所产生的影响应该如何计算

    (3)在线社交网络信息传播规律与演化机理。

    1. 信息的内涵如何以可计算的形式来表达
    2. 信息在社交网络上的传播过程与态势的计算方法是什么?
    3. 如何用计算的方法来刻画信息内涵与信息传播之间的相互影响?

    3 国际学术界高度关注社交网络研究(已有)

    在线社交网络分析涉及计算机科学社会学管理学心理学等多个学科领域。

    3.1 社交网络的结构特性研究

    (1)社交网络的结构分析与建模(基础

    1. 社交网络结构分析是通过统计方法来分析网络中节点的分布规律、关系紧密程度、相识关系的紧密程度,某一个用户对于网络中所有其他用户对之间传递消息的重要程度等诸多统计特性。

    2. 社交网络建模是针对社交网络的特性,采用结构建模的方法来研究产生这些特性的机制,以此来深刻认识社交网络的内在规律和本质特征。(图论方法)

    (2)虚拟社区发现(必备功能)

    1. 社会学领域,社区是一群人在网络上从事公众讨论,经过一段时间,彼此拥有足够的情感之后,所形成的人际关系的网络。社交网络中存在关系不均匀的现象,有些个体之间关系密切,有些关系生疏,从而在常规的社区之上围绕某一个焦点又形成了联系更为密切的社区形式,这可以看作社交网络中的虚拟社区结构。
    2. 虚拟社区结构是在线社交网络的一种典型的拓扑结构特征。

    (3)社交网络演化分析

    动态演化性

    3.2 社交网络中群体互动研究

    (1)社交网络上的用户行为分析

    社交网络上群体行为分析的已有研究主要集中在群体社交网络选择模型研究,以及个体行为特征分析等2 个方面。在群体社交网络选择模型研究方面,2007 年,美国密歇根大学的埃里森(Ellison)等人将社交网络的群体行为关系分为桥接型、黏接型和维持型三种类型,并基于回归分析发现**桥接型**关系对个体选择社交网络有着更重要
    的影响。

    (2)群体情感建模与行为互动

    情感分析是针对主观性信息(“支持”、“反对”、“中立”)进行分析、处理和归纳的过程,主观性信息表达了人们的各种情感色彩和情感倾向。社交网络中每个人情感状态不同,影响力也会不同。

    3.3 社交网络中的信息传播研究

    特指:以社交网络为媒介进行的信息传播过程。

    信息传播是人们通过符号信号来进行信息的传递、接收与反馈的活动,是人们彼此交换意见、思想、情感,以达
    到相互了解和影响的过程。

    (1)社交网络的信息及其能量

    已有研究主要集中在信息的符号表示与意义,以及信息传播能量及演化方面。

    (2)社交网络信息传播模型

    已有研究主要集中在传染病模型、网络拓扑图模型以及基于统计推理的信息传播模型等。

    (3)社交网络信息传播影响(热点)

    其目的是发现社交网络中最有信息传播影响力的节点集合,从而经过信息在社会网络中的传播,最终能够最大化信息的传播范围。在实际生活的许多重要场景中,社交网络信息传播影响分析均有着广泛的应用,例如,市场营销、广告发布、舆情预警、水质监测、疫情监控、网络竞选、突发事件通知等。

    研究方法:有概率论方法、经济学方法和传播学方法。

    概率论方法:基于概率图模型对研究信息传播的敏感度和影响力的方法,可以对概率图参数结构的重要性进行量化分析。

    4 我国在社交网络分析方面的研究进展

    4.1 主要研究单位

    国防科技大学、上海交通大学、合肥工业大学、北京邮电大学、中科院计算所、北京大学、清华大学、北京科技大学、浙江大学、哈尔滨工业大学、中科院信工所等单位都开展了系统性的研究。

    4.2 主要成果

    1. 结构分析方面,2009 年,中科院计算所的程学旗等人分析了社区结构的特性,改进了网络层次化重叠社区的发现方法,能够同时揭示网络的层次化和重叠社区结构。
    2. 群体特性方面,2009 年,合肥工业大学杨善林等人利用元胞自动机仿真从众行为,发现当群体出现完全从众行为时,从众行为的结果对初始状态相当敏感,不同的初始状态就可能有不同的演化结果。
    3. 信息传播方面,2004 年,北京理工大学邢修三提出了以表述信息演化规律的信息熵演化方程为核心的非平衡统计信息理论,从定量的角度对信息演化机理进行了有益的探索。
    4. 方滨兴等人也在系统梳理国内外相关理论和技术的基础上,编著了**《在线社交网络分析》**一书,从上述3 个角度入手为相关研究者提供理论性、系统性、工具性的研究指导。

    5 社交网络研究尚有诸多问题亟待突破

    国际上人们对于大型社交网络的本质特征和网络信息传播的基本规律的研究仍处在相对初级的阶段,尚未提出完整的社交网络分析的基础理论和方法,仍然值得我们进一步进行研究和突破。

    5.1 社交网络的一些挑战

    1. 在线社交网络的结构具有节点海量性、结构复杂性和多维演化性等特点,拓扑结构随着时间不断演变,对社交网络结构演化规律还需要进一步有效的表达和计算加以解决。
    2. 在线社交网络的信息传播具有信息的多源并发性其相互影响形成了路径多变和内容演化的特点。网络群体方面,已有研究对其产生、发展、消亡规律的内部交互作用机理知之不深;传统的群体建模及其互动方法无法准确刻画大规模在线社交网络中的强互动演变、公众情绪漂移等特征,不能真实分析出舆情的倾向性。在个体行为特征分析方面,传统的研究主要局限于用户个性化模型及其对社交网络的选择分析上,未涉及个体向群体演化过程中的个体行为表征等问题。
    3. 在线社交网络的群体互动具有强互动演变、公众情绪漂移等特征点,公众立场不断变化,兴趣点不断演化。已有的信息传播模型多基于传染病模型、网络拓扑图以及统计推理等方法,在描述社交网络传播模式以及计算效率和精度方面仍存在不足。研究视角上,尚缺乏从信息传播的时间、空间特征以及信息传播的双向性3 个维度,对信息传播的内在机制进行深度分析。传统理论和方法局限在“还原论”的角度解决问题,不能准确描述在线社交网络中信息的多源并发性所带来的相互影响等特性,因此需要研究新理论与新方法,以便在信息传播的相互作用中形成对舆情的驾驭能力。

    5.2 社区发现面临的一些挑战

    1. **社区的重叠性。**传统的社区发现研究一般基于“每一个节点都唯一归属于某个社区”的假设,而在现实社会网络中,**人们往往同时属于不同的社区,**而这种同时属于多个社区的人又是信息传递、社会交往中的关键。因此,针对重叠社区发现的研宄应得到研宄者的重视和关注。
    2. 社区的局部性。传统的社区发现算法很多都基于全局的信息,例如GN算法中的"边介数”、基于随机游走的算法中任意两点间的相似度、基于模块度的算法中的模块度等,都必须在考虑整个网络结构的前提下才能得出。随着信息化程度的不断提高,社会网络规模越来越庞大,获得网络的全局信息变得十分困难,而且这些社区发现算法在海量社会网络数据下显得非常低效。另一方面,社会网络通常是稀疏的,绝大多数个体与外界的直接联系都是有限的,而很多研究和应用都只关心某些节点所在的局部结构。甚于这些考虑,局部社区的概念被提出,相关问题需要进一步深入研究。
    3. 网络的多模式性与多维性。传统的网络分析中的节点对象通常是单一类型的,如:节点只代表了人、用户或者网页其中的一种,而多模式网络中的节点类型则是多样化的。比如社交网络中的某个用户分享的项目种类是多样化的,包括图片、视频、日志等,与其将这些交互的不同类型实体建模为节点的不同属性,不如建模为多模式网络更为方便。网络的多维性是指网络中的节点(用户)之间的边(连接)具有多种类型,而由这些节点及不同类型的边所组成的不同“维度”的网络(图)就称之为多维度网络。其中,每一个维度的网络表示了节点间不同类型的联系(互动),而边上往往又附带有权值信息,其代表了节点间互动的程度与连接的强度。因此,传统的对于单一模式、单个维度网络的单一分析在这里己经不再适用,如何在多模式、多维度网络当中解决不同模式及维度下的信息融合、共享以及进行社区发现等相关问题也亟待解决。
    4. 网络节点角色的差异性。传统的图挖掘、网络分析方法,并没有将网络中每个节点角色进行过多的区分,认为节点的地位是等同的。实际上,在各种复杂网络中尤其是社会网络中,都存在着帕累托效应(二八规则),即节点的角色存在着差异。只有大约百分之二十甚至更低比例的节点,在网络中发挥了领袖节点的作用,它们更具有权威性、中枢性、核心型等特征。同时也具有更多的经验和影响力,对社区的形成起着决定性的作用,对网络拓扑结构的演化、网络中的信息流通和传播有重大影响。在应用和分析中,首先应确定此类关键节点的存在性。而社会网络往往具有更为庞大的规模,如何快速有效地挖掘此类成员成为一个挑战性的问题。
    5. **网络的动态性。传统的社区研宄一般是针对静态的网络展 研宄的,这种研究视角不能很好地反映诸如信息扩散、同步等动态过程。研究网络的动态性的目的在于揭示网络拓扑结构对发生在其上的动态过程的影响,以及这些动态过程是否能够反映其“承载网络”的拓扑结构特征。研究社区结构和网络动态性的关键在于社区演化问题,**其主要关注网络自身结构和在其上频繁发生的交互过程相互作用的结果,如社区形成、社区生长、社区缩减、社区合并、社区分裂、社区消亡等。

    6 对社交网络研究问题的思考

    结构、群体是为传播研究而服务的。

    社交网络分析的3 个要素“结构”、“群体”和“传播”是相互作用的关系。社交网络结构建模和群体互动规律分析的目标都是支持信息传播形态研究,因此是否能够将结构建模与群体互动者两个独立的要素结合起来,研究结构与互动相结合的动态建模方式?已有的信息传播过程分析中,核爆炸式、烟花式、星球式、水母式等信息爆发式传播形态都能客观表示,如何能够让拓扑结构建模对这些信息传播的模型有所贡献?如何从结构建模的角度支持这些外显形态的存在?群体事件、群体极化、群体演化等社交网络中的群体形态是否也能被模型化?信息传播的影响力是否能够形成一个可计算的量纲?如何将碎片化、时变的、演化的话题分析技术和信息传播、溯源技术结合起来,形成信息传播的可计算模型。

    作为一种新型媒介,在线社交网络的根本在于信息流动和传播,而信息的传播根植于社会群体的互动,但又受限于社交结构与社区的规模

    信息传播过程可以被视作社交网络中一个时间函数的求解变量,其中的群体正是函数因子,而社交网络的拓扑结构是控制其发展的边界条件。21 世纪,是人类高度依赖数据、深度融入信息社会的世纪。在信息社会中,在线社交网络构建了庞大的功能平台。人们在社交网络上表达观点、交友互动,每天都产生数亿计的信息。

    在线社交正在改变着人们的行为模式和社会形态,而在线社交网络数据也正在成为最成熟的大数据,通过研究和分析这一技术,人们有望对在线社交网络大数据背后的用户行为、社会现象的理解达到空前的深度。

    7 社交网络分析的应用

    7.1 社交推荐

    社交推荐顾名思义是利用社交网络或者结合社交行为的推荐,具体表现为推荐 QQ 好友,微博根据好友关系推荐内容等。在线推荐系统最早被亚马逊用来推荐商品,如今,推荐系统在互联网已无处不在,目前大热的概念“流量分发是互联网第一入口”,支撑这个概念有两点核心,其一是内容,另外就是推荐,今日头条在短短几年间的迅速崛起便是最好的证明。

    根据推荐系统推荐原理,社交推荐可定义为一种“协同过滤”推荐,即**不依赖于用户的个人行为,而是结合用户的好友关系进行推荐。**对于互联网上的每一个用户,通过其社交账户能很快定义这个用户众多特点,再加之社交网络用户数之多,使得利用社交关系的推荐近些年备受关注。

    7.2 舆情分析

    舆情分析在互联网出现之前就被广泛应用在政府公共管理,商业竞争情报搜集等领域。在社交媒体出现之前,舆情分析主要是线下的报纸,还有线上门户网站的新闻稿件,这些信息的特点是相对专业准确,而且易于分析和管理;但随着社交媒体出现,舆情事件第一策源地已经不是人民日报新华社这样的大媒体,而是某一个名不见经传的微博用户,一个个人微信公众号。他们的特点是信息非常新鲜,缺点是真实度较低且传播十分迅速,难以控制。所以在社交网络下的舆情分析是一门新的学问。

    “刺死辱母者”微博转发趋势

    举几个例子,去年的和颐酒店,今年的北京地铁骂人事件这类急性舆情事件最早就是在微博上爆出,而且在短时间内迅速传播。还有去年的关于快手的“中国农村残酷底层物语”,今年的“北京房价”等这类民生话题,也是在微信公众号逐渐发酵。

    当然,在新形势下的舆情应对,也已经有新的工具,大家百度“舆情分析平台”或者“舆情分析软件”可以找出一大堆。比较有名的有蚁坊、红麦、清博、知微、新榜等等。一些传统的舆情分析机构开始转型做“大数据”的舆情分析,也有近年来完全基于社交媒体的舆情平台,比如基于微信的新榜和基于微博的知微 。除此之外,BAT 等大型平台有自己舆情分析工具,可以私人订制,也有开放的指数(百度指数、微信指数)。

    7.3 隐私保护

    隐私问题在互联网时代已经是老生常谈的问题了。在社交网络中,作为用户,我们可能会留下大量痕迹,这些痕迹有隐性的,也有显性的,好不夸张地,社交服务提供商可以根据你的少量痕迹,挖掘到大量你的个人信息,有些信息是你不愿意别人知道的。

    这其中存在一个矛盾,即社交服务提供商处于商业目的想尽可能获取你的个人信息,但是你又担心自己的个人信息被泄露。所以在隐私保护领域,一方面要设计足够安全的机制,技术层面的,法律层面的,在保护个人隐私的前提下最大化商业利益和用户的体验。

    举一个大家比较熟悉的例子,即许多网站注册账户的时候使用微信、支付宝账户验证,即免去了大家填写个人信息的烦恼,又保护了大家的隐私。同理,蚂蚁金服提供的芝麻信用功能也有隐私保护的功能。

    目前学界对隐私保护的研究主要还是从技术层面设计完善的隐私保护机制。

    7.4 用户画像

    用户画像,这是个营销术语,即通过研究用户的资料和行为,将其划分为不同的类型,进而采取不同的营销策略。传统的用户画像最常用的手段就是调查问卷,订阅过杂志和报纸的读者都知道,会有各种各样的有奖问卷,一方面用来获得对于产品的反馈,另一方面就是对你进行画像,这些画像资料甚至广泛在黑市流通,这就是你为什么有时候会接到莫名其妙的电话的原因(又扯到了隐私保护问题)。

    在社交网络,用户画像方式变得更多了,除了传统的线下问卷变成在线问卷。我们通过用户的行为,一方面通过统计学方法获得一些用户特征(经典的例子是沃尔玛的“啤酒和尿布”,另一方面通过机器学习进行建模和验证获得意外的收获(参见上面提到的腾讯社交广告文章)。

    接触过微信公众号后台的读者都知道,公众号后台对微信公众号文章的读者还有公众号粉丝的画像已经做得非常充足了,好像微博会员也有粉丝画像的功能。这些便捷的功能对于媒体运营者和广告投放者都有非常重要的作用。

    7.5 谣言检测

    谣言检测算是舆情分析的一部分,之所以单独提出来是因为这部分非常重要,而且谣言的确定对于舆情管理非常重要。早起微博因为充斥着大量谣言,使得新浪微博不得不推出“微博辟谣”官方账号,到如今微博以及有许多自发和官方的辟谣账号,微信公众号也是如此。

    传统辟谣方法无非是进行试试检验,用证据说话,随着现在机器学习技术的迅速发展,我们也可以通过信息传播的轨迹,信息内容等维度自动判断消息是否属于谣言,而且判断地越迅速,对于舆情管理的意义就越大。同理,这种技术也被应用在社交网络有害信息识别。

    在国外,有关 Facebook 假新闻的新闻被炒得火热,有兴趣的读者可以关注一下。

    7.6 可视化

    可视化是随着大数据一起成为热门话题的。因为人类对于图像信息的理解速度要大于文字信息数百倍,所以讲一些数据可视化有助于人们更生动地理解某一结论或现象。当然不是所有数据都适合可视化,在社交网络中,我们最常见的有信息传播轨迹还有词云图等。有关这方面的内容可以参考微博账号“社交网络与数据挖掘”。

    除了专门可视化的机构,网上也有许多开源的可视化库,百度的 Echarts 就很有名。 对于社交网络信息传播以及好友关系等的可视化,使得我们能直观看到一些事实,这对于舆情报告制作以及新闻报道都有很好的辅助作用。

    8 学习资料

    8.1 图书

    • 《社会计算》Lei Tang, Huan Liu

    • 《社交网站的数据挖掘与分析》Matthew A. Russell

    • 《在线社交网络分析》 方滨兴等

    • 《社交媒体挖掘》Huan Liu等

    • 《大话社交网络》郎为民

    8.2 网站

    • 大数据导航(此网站包含很多资源)

    http://hao.199it.com/

    • 斯坦福数据集网站(Jure 男神)

    http://memetracker.org/data/index.html

    • 加州大学欧文分校数据集网站

    http://archive.ics.uci.edu/ml/datasets.html

    • 国内社交网络数据集共享网站

    http://www.socialysis.org/data/project/project

    • 清华大学搭建的学术数据库

    https://cn.aminer.org/

    • 亚马逊商品流行趋势分析平台

    http://132.239.95.211:8080/demowww/index.jsp#

    • 明尼苏达双城分校社会计算实验室

    https://grouplens.org/

    • 新华网信息传播影响力评估

    http://www.xinhuanet.com/xuanzhi/zt/xzyxl/index.html

    • 新榜,微信公众号数据检测平台

    http://www.newrank.cn/

    • 清博新媒体大数据平台

    http://www.gsdata.cn/

    • 百度Echarts数据可视化库

    http://echarts.baidu.com/

    • 阿里云 DataV 数据可视化库

    https://yq.aliyun.com/teams/8

    8.3 工具

    • Python 及其相关库(scipy,numpy,pandas,scikit,scrapy,twitter )更多请见 http://blog.csdn.net/hmy1106/article/details/45166261

    • 图分析分析工具 Graphchi,SNAP,Pajek,Echarts

    • 可视化工具 Gephi,Graphviz

    • 数据挖掘工具 WEKA,AlphaMiner

    • 图数据库 Neo4j

    8.4 会议

    笔者仅列出与社交网络相关的部分国际会议,排名不分先后,加粗的会议为专门讨论社交网络话题的会议。

    KDD, WWW, ICDM, CIKM, AAAI, SDM, IEEE BigData, ASONAM, WSDM, ICWSM, ACL, IJCAI, NIPS, ICML, ECML-PKDD, VLDB, SIGIR, PAKDD, RecSys, ACM HT, SBP, ICWE, PyData

    笔者在这里推荐两个国内的社交网络分析会议,一个是全国社会媒体处理大会(SMP),由中国中文信息学会主办,会议论文 EI 检索。第二个是国际网络空间数据科学会(IEEE ICDSC),会议由中科院,北大,中国网络空间安全协会等机构筹办。

    8.5 课程

    笔者在上一部分提到的国际会议,例如 WWW、KDD 等,每年都有关于社交网络分析方向的 tutorial,其视频和 PTT 都是在网上可获取的,通过 tutorial 能对相关领域有一个宏观了解并且能了解领域前沿动态。

    除此之外,在 Coursera 上面密西根大学安娜堡分校开设的一系列 Python 学习课程也值得一看。在网易公开课上面也有中文的 Python 数据挖掘课程可供学习。

    万能的淘宝也提供大量廉价的视频和电子学习资料。

    最后,利用好科学上网工具和搜索引擎(不是百度)才是王道。

    8.6 参考资料

    [1] 方滨兴, 许进, 李建华. 在线社交网络分析[M]. 电子工业出版社, 2014.

    [2] Reza Zafarani, Mohammad Ali Abbasi, Huan Liu. 社会媒体挖掘[M]. 人民邮电出版社, 2015.

    [3] Carlos Castillo, Wei Chen, Laks V.S. Lakshmanan, Information and Influence Spread in Social Networks,KDD 2012 Tutorial

    [4]中国知网(中科院院刊)社交网络分析核心科学问题、研究现状及未来展望

    基金项目:国家重点基础研究发展计划(“973”)项目(2013CB329601),国家自然科学基金项目(61372191)

    展开全文
  • 复杂网络之社交网络

    千次阅读 2017-11-28 11:02:39
    可以说,网络生活已经渗透到了我们现实生活中的方方面面,二者不仅相互关联和相互影响,其中一些领域已经发展到互补关系甚至代替关系。无论是在网络空间还是现实空间,人与人之间都会存在着由工作、出行、休闲等原因...

    移动互联网在近年来经历了快速的发展,全球用户数已接近30亿。人们在移动互联网上享受着各种便利的服务,如交友、点餐、求职、阅读新闻、观看视频、发布照片、分享旅行等等。可以说,网络生活已经渗透到了我们现实生活中的方方面面,二者不仅相互关联和相互影响,其中一些领域已经发展到互补关系甚至代替关系。无论是在网络空间还是现实空间,人与人之间都会存在着由工作、出行、休闲等原因而产生的各种关系。我们的日常行为或多或少都会受到社交关系的影响。比如,我们会购买朋友推荐的商品,去某一个公司拜访客户,或者和家人一起去某个城市度假。

    过去,由于缺乏相关数据,人们只能孤立地研究人类行为在不同空间的特征,而移动互联网的兴起,特别是同时包含了社交关系和位置信息的LBSN(Location-based SocialNetworks)数据为研究人类行为在不同空间和层面上的关联扫清了障碍。现有的研究估计,人们日常生活中有10%-30%的出行以社交为目的[1],那些居住距离较近的人们有更大的几率成为好友[2]。同时,人们出行轨迹的相似性和他们社交网络的接近性存在显著的正相关关系,即好友之间的轨迹相似性要高于非好友[3],反过来,轨迹相似性高的好友往往在社交网络上也有着较高的通信频率和共同好友数[4]。那么,人们在网络空间和现实空间里的行为的相似性该如何度量?它们是否相关?一对用户在网络空间的相似,是否意味他们在现实生活中的行为也相似呢?为了回答这些问题,我们在一组腾讯QQLBSN数据上进行了系统地分析。

    我们用余弦相似度来定义用户出行轨迹的相似性,用是否是好友是否有共同好友共同好友的个数以及共同好友的多样性(以共同好友网络中连通子图的个数来度量)这四个指标来描述好友之间的社交网络接近性[4,5]。统计结果显示,相比非好友,好友之间的平均轨迹相似性要高的多,而有共同好友则会进一步提升彼此的相似性。出乎意料的是,在相关系数、概率分布和假设检验等多种统计工具的支撑下,我们发现共同好友的数量并不会对用户之间的轨迹相似性产生积极作用,反而是那些共同好友的多样性更强的用户有着更高的轨迹相似性(具体分析方法请见文献[6])。也就是说,共同好友的来源多样性在影响好友之间的轨迹相似性上有着比数量更为重要的作用。我们进一步使用其它相似性指标重复实验,验证了结果的鲁棒性。

    我们的研究不仅建立了人类行为相关性的分析框架,而且对于寻找行为相似性更高的用户进行轨迹预测[7]、商品推荐[8]、链路预测[9]等场景都有着直接或潜在的应用价值。

    参考文献:

    [1] Cho, E., Myers, S. A.& Leskovec, J. Friendship and mobility: User movement in location-basedsocial networks. In Proceedings of the 17th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, 1082–1090 (ACM, 2011).

    [2] Liben-Nowell, D., Novak,J., Kumar, R., Raghavan, P. & Tomkins, A. Geographic routing in socialnetworks. Proc. Natl. Acad. Sci. USA 102, 11623–11628 (2005).

    [3] Toole, J. L., Herrera-Yaqüe,C., Schneider, C. M. & González, M. C. Coupling human mobility and socialties. J. R. Soc. Interface 12, 20141128 (2015).

    [4] Wang, D., Pedreschi, D.,Song, C., Giannotti, F. & Barabási, A.-L. Human mobility, social ties, andlink prediction. In Proceedings of the 17th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, 1100–1108 (ACM, 2011).

    [5] Ugander, J., Backstrom,L., Marlow, C. & Kleinberg, J. Structural diversity in social contagion.Proc. Natl. Acad. Sci. USA 109, 5962–5966 (2012).

    [6] Fan, C. et al. Correlationbetween social proximity and mobility similarity. Scientific Reports 7, 11975(2017).

    [7] Lian, D. et al. MiningLocation-Based Social Networks: A Predictive Perspective. IEEE Data EngineeringBulletin 38, 35–46 (2015).

    [8] Lü, L. et al. Recommendersystems. Physics Reports 519, 1–49 (2012).

    [9] Lü, L. & Zhou, T. Linkprediction in complex networks: A survey. Physica A: Statistical Mechanics andits Applications 390, 1150–1170 (2011).

    论文信息:

    Chao Fan, Yiding Liu, Junming Huang, Zhihai Rong, TaoZhou. Correlation between social proximity and mobility similarity. Scientific Reports, 2017, 7: 11975.

    论文链接(可免费下载):

    https://www.nature.com/articles/s41598-017-12274-x


    这个研究给轨迹预测等研究提供了很好的特征建议。社会关系应该不仅限于远近(Weight),还有不同的类型(Type),比如朋友、同事、远亲、近邻、爱人、孩子等等,有没有这方面的研究工作,以及将类型分开应用的价值如何?


    展开全文
  • 社交网络分析算法(SNA)

    万次阅读 2017-10-30 22:11:11
    近来学习聚类,发现聚类中有一个非常有趣的方向—社交网络分析,这篇只是一篇概况,并没有太多的公式推导和代码,基本是用人话解释社交网络分析中的常用的几种算法。详细到每个算法的以后有空再把详细的公式和代码补...

    近来学习聚类,发现聚类中有一个非常有趣的方向—社交网络分析,这篇只是一篇概况,并没有太多的公式推导和代码,基本是用人话解释社交网络分析中的常用的几种算法。详细到每个算法的以后有空再把详细的公式和代码补上。
    目录:
    1.应用场景
    2.分析指标
    3.社区发现算法
    3.1 GN算法
    3.2 Louvain算法
    3.3 LPA与SLPA

    1. 应用场景

    社交网络分析中最常用的就是社交圈子的识别,所谓物以类聚,人以群分,一旦能对社交圈子进行分类,能做的事情就会很多。

    FaceBook和微信是关于人与人之间的强关系网络,划分社交圈有助于朋友间相互推荐。
    领英是关于职业的社交的社交网络,有助于求职和商务合作交流。
    微博,Twitter,豆瓣,微信公众号是关于关注与被关注的的弱关系网络,有助于消息和知识的传播。

    分好社交网络之后可以对人进行精准化营销,推荐个性化的商品和服务,比如京东;
    疾病传播也是由一个中心点向外扩散,切断网络中的关键节点就可以有效阻止传染病的传播;
    识别互联网金融行业中的欺诈团伙,进行反欺诈预测;

    这只是其中的三个方面,还有很多应用在此不作细讲。

    2.分析指标

    图,简单来说就是人物(事物)关系的形象化表示。节点(node)代表一个人物,边(edge)代表人物关系。有向图用箭头表示人物间的关系,无向图用线段表示人物间的关系。
    顺便提供两份图数据集,可以自己拿来做实验:
    斯坦福大学实验数据

    网络分析数据集

    这里重点讲述社交网络算法的分析指标。

    度(Degree)
    连接点活跃性的度量;与点相连的边的数目。在有向图中,以顶点A为起点记为出度(out degree)OD(A),以顶点A为终点入度(In degree)ID(A),则顶点A的度为D(A) = OD(A) + ID(A)。
    Igraph是图计算和社交网络分析的常用工具,提供了python的接口,安装方式参考官网:Igraph官网点这

    这里写图片描述

    算了,还是拿权游的数据玩一下比较爽。
    计算度:

    import csv
    edges = []
    firstline = True
    with open('/Users/huanghuaixian/desktop/stormofswords.csv','r') as f:
        for row in csv.reader(f.read().splitlines()):
            if firstline == True:
                firstline = False
                continue
            u,v,weight = [i for i in row]
            edges.append((u,v,int(weight)))
    from igraph import Graph as IGraph
    g = IGraph.TupleList(edges ,directed = True ,vertex_name_attr = 'name' ,edge_attrs = None ,weights = True)
    print(g)
    for p in g.vs:
        print(p['name'],p.degree())

    分析一下网络结构:

    #角色数
    g.vcount()
    #143个角色
    #网络直径,网络中最长最短路径
    print(g.diameter())
    #输出7

    最短路径

    print(g.shortest_paths("Sansa","Margaery"))
    print([ names[x] for x in g.get_all_shortest_paths("Sansa","Margaery")[0]])
    for p in g.get_all_shortest_paths('Sansa'):
        print([names[x]for x in p])
    #输出1和所有以Sansa开始的最短路径

    紧密中心性(closness centrality)
    节点V到达其他节点的难易程度,也就是到其他所有节点距离的平均值的倒数。
    这里写图片描述
    代码实现:

    ccvs = []
    for p in zip(g.vs, g.closeness()):
        ccvs.append({"name": p[0]["name"], "cc": p[1]})
    sorted(ccvs, key=lambda k: k['cc'], reverse=True)[:10]

    [{‘cc’: 0.5120772946859904, ‘name’: ‘Tyrion’},
    {‘cc’: 0.5096153846153846, ‘name’: ‘Sansa’},
    {‘cc’: 0.5, ‘name’: ‘Robert’},
    {‘cc’: 0.48847926267281105, ‘name’: ‘Robb’},
    {‘cc’: 0.48623853211009177, ‘name’: ‘Arya’},
    {‘cc’: 0.4796380090497738, ‘name’: ‘Jaime’},
    {‘cc’: 0.4796380090497738, ‘name’: ‘Jon’},
    {‘cc’: 0.4796380090497738, ‘name’: ‘Stannis’},
    {‘cc’: 0.4690265486725664, ‘name’: ‘Tywin’},
    {‘cc’: 0.4608695652173913, ‘name’: ‘Eddard’}]

    介数中心性(betweenness centrality)
    核心思想是两个非邻接成员间的相互作用依赖于网络中的其他成员,特别是两成员间路径上的成员,它们对两非邻接成员间起着某种控制或依赖关系。如果一个成员A位于其他成员的多条最短路径上,那么成员A的作用就比较大,也具有较大的介数中心性。
    本质:网络中包含成员B的所有最短路径条数占所有最短路径条数的百分比。
    计算公式如下:
    这里写图片描述
    计算步骤:
    1.计算每对节点(i,j)的最短路径(需要得到具体的路径)
    2. 对各节点判断v是否在最短路径下
    3. 累加经过v的最短路径条数

    #偷懒一下
    btvs = []
    for p in zip(g.vs, g.betweenness()):
        btvs.append({"name": p[0]["name"], "bt": p[1]})
    sorted(btvs, key=lambda k: k['bt'], reverse=True)[:10]

    结果:

    [{‘bt’: 332.9746031746032, ‘name’: ‘Tyrion’},
    {‘bt’: 244.63571428571433, ‘name’: ‘Samwell’},
    {‘bt’: 226.2047619047619, ‘name’: ‘Stannis’},
    {‘bt’: 208.62301587301587, ‘name’: ‘Robert’},
    {‘bt’: 138.66666666666666, ‘name’: ‘Mance’},
    {‘bt’: 119.99563492063493, ‘name’: ‘Jaime’},
    {‘bt’: 114.33333333333334, ‘name’: ‘Sandor’},
    {‘bt’: 111.26666666666665, ‘name’: ‘Jon’},
    {‘bt’: 90.65, ‘name’: ‘Janos’},
    {‘bt’: 64.59761904761905, ‘name’: ‘Aemon’}]

    3 . 社区发现算法

    社区相当抱团,类似群的概念,同一个社区内的连接紧密,而社区间的连接非常稀疏。社区发现可以理解为在图中发现n个社区,他们连接非常紧密。

    3.1 GN 算法

    边介数(betweenness):网络中经过该边的最短路径占所有最短路径的比例。
    GN算法计算步骤:
    1. 计算网络中所有边的介数
    2. 找到介数最高的边,并将它从网络中移除
    3. 重复以上步骤,直到每个节点就是一个社区为止。
    这里写图片描述

    3.2 Louvain 算法
    Louvain算法是基于模块度的算法,其优化目标就是最大化整个社区网络结构的模块度。

    模块度
    它的物理含义是社区内节点的连边数与随机情况下节点的连边数之差,它可以衡量一个社区紧密程度的度量。因此模块度就可以作为优化函数优化社区的分类。
    计算方法如下:
    这里写图片描述
    其中Aij是节点i与节点j之间的权重,网络不是带权图时,所有边的权重看作是1;ki=jAij表示所有与节点i相连的权重之和;ci表示节点i所属的社区;
    m=12ijAij表示所有边的权重之和,取值范围:[-1/2,1)。

    算法思想
    1. 不断遍历网络中的节点,尝试把单个节点加入能使模块度提升最大的社区,直到所有节点不再改变
    2. 将第一阶段形成的一个个小的社区并为一个节点,重新构造网络。这时边的权重为两个节点内所有原始节点的边权重之和。
    3. 重复以上两步

    更多请参考:点这

    3.3 LPA与SLPA

    LPA算法思想:
    1. 初始化每个节点,并赋予唯一标签
    2. 根据邻居节点最常见的标签更新每个节点的标签
    3. 最终收敛后标签一致的节点属于同一社区

    SLPA算法思想:
    SLPA是LPA的扩展。
    1. 给每个节点设置一个list存储历史标签
    2. 每个speaker节点带概率选择自己标签列表中标签传播给listener节点。(两个节点互为邻居节点)
    3. 节点将最热门的标签更新到标签列表中
    4. 使用阀值去除低频标签,产出标签一致的节点为社区。

    参考:
    代码部分取自该博客
    七月在线算法课程课件
    概念解释的通俗易懂

    展开全文
  • 用python分析《三国演义》中的社交网络

    千次阅读 热门讨论 2018-12-30 12:24:28
    一直以来对自然语言处理和社交网络分析都很感兴趣,前者能帮助我们从文本中获得很多发现,而后者能够让我们对人们和各个事物之间普遍存在的网络般地联系有更多地认识。当二者结合,又会有怎样的魔力呢? 作为一个...
  • 社交网络最大化

    2019-01-14 10:13:03
    其强度取决于多种情况,如网络中人与人之间关系的亲密程度,网络中人与人之间的距离,时间因素,网络网络中个人的特点。 对于代表性影响力度量的理解与实现: 中心性(Centrality):对于具有更多连接关系的结点...
  • 由Visio绘制的社交网络图,可扩展至其他方面。主要有一幅图以及图例。
  • 社交网络数据集

    2020-07-29 14:20:17
    可以用于复杂网络学习,网络结构研究,如社团划分发现等
  • 如何使用python进行社交网络分析

    万次阅读 2017-03-13 17:06:44
    Social Network Analysis for Startups 是一本介绍如何使用python进行社交网络分析的入门书,主要使用了NetworkX、numpy等插件进行网络分析,前端可以使用Matplotlib进行可视化展示,一个展示效果图如下所示: ...
  • 社交网络中常用数据集

    千次阅读 2016-06-02 09:00:44
    Meetup数据集该数据集爬取自...在Meetup上,社会事件由用户通过指定事件在何时何地发生了什么创造。然后创造的社会事件就可以选择用户或者公众参加,这些由事件的创造者控制。其他用户可以表达他们参与事件的意愿。...
  • 社交网络中的社区发现算法

    千次阅读 2018-01-07 23:54:58
    本博客主要是对Finding and evaluating communitystructure in networks ——Girvan,Newman 该论文的解读。 介绍 相关定义 ...通过删边
  • 社交网络看成图社交网络的基本概念: 社区(community):是指具有非同寻常的强连通性的节点子集,其中节点可以是构成网络的人或者其他实体。 局部性(locality):是指社交网络的节点和边趋向于聚为社区的这种...
  • 社交网络影响力最大化

    万次阅读 2019-07-06 21:31:07
    1、社交网络概述 2、影响力最大化问题分类 3、社交网络影响力最大化作用 4、传播模型 4.1独立级联模型(Independent Cascade Model)简称 IC 模型 4.2线性阈值模型(Linear Threshold Model)简称LT模型 社交...
  • 社交网络——新一代数据挖掘的金矿   随着Facebook的上市,社交网络再次成为人们关注的焦点。与传统的论坛、博客相比,社交网络是虚拟世界与现实世界的桥梁,在互联网上将现实生活中人与人之间的关系建立起来...
  • 随着移动互联网时代的到来,UGC(用户产生内容)不断发展,社交网络(Social Network)已经不断普及并深入人心,用户可以随时随地在网络上分享内容,由此产生了海量的用户数据。面对大数据时代的来临,复杂多变的...
  • 社交网络,对每个人是熟悉而又陌生的。每个人都可以说出个一二三,因为人是社会的动物,每个人都有自己的社交圈子即社交网络。然而,就社交网络的应用尤其是移动互联网社交应用而言,尽管创业团队不停地涌现,或...
  • 利用python、Gephi绘制人人的社交网络

    万次阅读 热门讨论 2013-06-07 20:59:06
    1. 登陆自己的人人网,进入到网页 http://friend.renren.com/myfriendlistx.do#item_0 ,得到如下图的页面: 右键查看源代码,将下图中自己好友列表的一行复制出来,保存为 myFriends.dat (保存为一行的...
  • 7个开源的SNS社交网络平台

    千次阅读 2015-07-01 17:49:40
     Dolphin是一个最受欢迎的社交网络构建系统,基于PHP+MySQL开发。提供的功能包括:100% AJAX论坛,照片共享,视频聊天,视频共享/播放,音乐共享,Blogs,群组,收发邮件,交友,自定义主题,桌面客户端等。   ...
  • 在线社交网络影响力分析——总结

    千次阅读 2014-08-07 19:05:03
    社交影响力可以通过用户之间的社交huo'dong
  • [转载]初学社交网络分析-《庶民的微胜利:R与社交网络分析》 关键词:igraph 图表输出 图形优化初次尝试igraph包 igraph包入门R语言画社交关系图 根据用户分享的歌曲,使用协同过滤算法计算歌手之间的关联关系。...
1 2 3 4 5 ... 20
收藏数 122,414
精华内容 48,965
关键字:

社交网络