c语言有向网络介数,SNA社交网络算法

社交网络需要用到igraph库，所以需要安装。可以在lfd的网站

http://www.lfd.uci.edu/~gohlke/pythonlibs/ 上下载python_igraph，具体的python对应版本和是32位还是64位的，比如我下载了 python_igraph‑0.7.1.post6‑cp35‑none‑win_amd64.whl

利用pip 安装whl文件：pip install文件名.whl

为了避免出错，打开cmd以后，要cd进入你存放的该whl文件的解压后的目录下在用pip进行安装。

一、社交网络算法介绍

应用场景：在社交网络中社区圈子的识别；基于好友关系为用户推荐商品或内容；社交网络中人物影响力计算；信息在社交网络上的传播模型；虚假信息和机器人账号的识别；互联网金融行业中的反欺诈。

什么是图：

节点代表人，边代表人与人之间的关系。

无向图(人人网)和有向图(twitter或豆瓣这种单向关注的属于有向图)。

二分图(两类不同的节点，u和v里面的节点没有连接)和多图(两个节点之间有多条边)

社交网络算法——分析指标：

一个具体的网络可以抽象为由一个节点集合V和边集合E组成的图G=(V,E)，节点数记为n=|V|，边数记为m=|E|。衡量指标(社交网络的分析性指标)包括

①度(结点直接关联的属性)

通俗点理解就是人有多少个朋友。无向图的话只有度，有向图的话有入度和出度。

②紧密中心性(closeness centrality)

某个结点到达其他结点的难易程度，也就是其他所有结点距离平均值的倒数。该数值越大，说明周围聚集的点越多。

(路径个数-1)/路径长度

方法1：自己写，Igraph中，有g.get_all_shortest_paths(‘7’) #获得7的所有最短路径

方法2：用igraph中的函数

③介数中心性(closeness centrality)

网络中的交通枢纽性，拿掉后网络会分裂开。

计算整个网络中任意两个节点的最短路径，当然需要得到具体路径

对各个节点判断该节点是否在最短路径上

最后将刚刚的判断进行累加得到从i到j的最短路径经过该节点的个数，比如数一下，经过7的最短路径有几条

点介数：

团(clique，团是比较紧密的结构，一个图中所有两两之间是有关系的)，如果在网络中找到这种团状的是可以发现网络中的一些特性的。

Clique为3的团

社交网络算法——PageRank算法：

思想：被大量高质量网页引用的网页也是高质量网页。最初会设置一个初始值，假设所有网页的一个权重是1/N(B0)，然后用A*B0去得到Bi(新的权重)，其中A还一个方正，比如有7个节点，就是7*7的矩阵，里面的值是每个节点之间边的数量。第三个公式是对第一个的优化，设定α的值，帮助更快的收敛。

Python中也有现成的包，其中参数damping就是α的值。

社交网络算法——社区发现算法：

什么是社区？同一社区内的节点与节点之间的连接很紧密，而社区与社区之间的连接比较稀疏。设图G=G(V, E)，所谓社区发现是指在图G中确定nc(>=1)个社区C={C1, C2,….Cnc}，使得各社区的顶点集合构成V的一个覆盖。

若任意两个社区的顶点集合的交集均为空则称C为非重叠社区，否则为重叠社区。

更加贴近于真实的网络情况，而聚类算法不允许一个点属于多个类。

社交发现算法——GN算法：

边介数(betweenness)：网络中经过每条边的最短路径的数目。

GN算法：计算网络中所有边的介数；找到介数最高的边并将它从网络中移除；重复，直到每个节点就是一个社团为止。GN算法的复杂度较高，做了一次全网遍历，计算边介数，时间消耗非常高。该算法是最经典的社区发现算法，利用分裂的思想来做的。其中不一定是要计算边介数，你也可以计算度、紧密中心性等等，你可以自己优化该算法。

边介数的计算：

社区评价指标——模块度(评价整个社区划分结果)：

模块度，利用了社区结构的定义，社区内的节点联系是比较紧密的，社区中两个节点有边的概率要高于随机图中两个节点有边的概率。Aij是邻阶矩阵(各节点之间相连通过的边数)，Ki是度数。

为1，如果i和j属于同一个社区，否则为0。

社区评价指标——阻断率conductance(单个社区的评估)：

连接到社区外的边数/社区内的节点连接的边个数。越小越好。

社区发现算法——Louvain算法：

该方法就是利用模块度来优化的一种方法。首先把每一个节点作为一个独立的社区，假设我们把J1加入到i会有一个模块度的增量，把J2加入到i会有一个模块度的增量..等等，从中选出模块度最高的一个邻居节点，加入i的社区中。这是一种启发式的凝聚算法。

社区发现算法——LPA算法(时间复杂度较低近似n，标签传播的思想)：

但该算法在工业界并没有很好的实践，稳定性并不是很好。优点：不需要预先知识，不用预先给定社区的数量，可以控制迭代的次数来划分节点类别。可扩展性强，时间复杂度近线性，适合处理大规模复杂网络。

算法思想：初始化每个节点，给其唯一标签；根据邻居节点最常见的标签更新每个节点的标签；最终收敛后标签一致的节点属于一个社区。

同步更新：可能存在最后不能收敛的情况。

异步更新：使用到上一次我的节点更新的信息

社区发现算法——SLPA算法(LPA算法的改进)

算法思想：给每个节点设置一个列表来存储历史标签；每个Speaker节点带概率选择自己标签列表中的标签传播给listener节点(Speaker节点为Listerner节点的邻居节点)；节点将最热门的标签更新到标签列表中；使用阈值r去删除低频标签，产出标签一致的节点为社区。(支持非重叠社区)

社交网络算法在金融反欺诈中应用

传统反欺诈主要是评分卡，其实就是逻辑回归，只是变量的选取会有一定的技巧。

应用社交网络反欺诈：客户一度、二度关系是否触黑；客户消费关联商家是否异常；一机多人；识别组团欺诈(离线情况下，社区划分，可能有些社区的违约率很高，我们就把他贴上拒贷用户的标签，对于新来的用户，就可以判断他属于哪个社区)

图论(floyd算法)：NOI2007 社交网络

[NOI2007] 社交网络 ★★   输入文件:network1.in   输出文件:network1.out   简单对比 时间限制:1 s   内存限制:128 MB [问题描述] 在社交网络( ...

【题解】Luogu P2047 社交网络总结 (Floyd算法，最短路计数)

题目描述 在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象.不妨看这样的一个问题.在一个社交圈子里有n个人,人与人之间有不同程度的关系.我 们将这个关系网络对 ...

算法练习_图的连通性问题(JAVA)

一.问题 1.问题描述: 有n个点(1...n),输入整数对(8,9),表示8,9点之间存在相互的连接关系. 动态连通性问题--编写一段程序过滤掉所以无意义的整数对,即为在不破坏图连通性的前提下,以最 ...

《社交网络》里的评分公式——ELO排名系统

里的Mark Zackburg被女朋友甩后,在舍友的启发下,充分发挥了技术宅男自娱自乐的恶搞天分,做出了Facemash网站,对学校女生的相貌进行排名打分,结果网站访问流量过大 ...

[Recommendation System] 推荐系统之协同过滤(CF)算法详解和实现

1 集体智慧和协同过滤 1.1 什么是集体智慧(社会计算)? 集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的,只是在 Web2.0 时代,大家在 Web ...

CF(协同过滤算法)

1 集体智慧和协同过滤 1.1 什么是集体智慧(社会计算)? 集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的,只是在 Web2.0 时代,大家在 Web ...

HipHop算法：利用微博互动关系挖掘社交圈

/* 版权声明:可以任意转载,转载时请务必标明文章原始出处和作者信息 .*/                  CopyMiddle: 张俊林 TimeStamp:2012年3 月 在微博环境下,如何 ...

PeopleRank从社交网络中发现个体价值

阅读导读: 1.什么是PeopleRank? 2.PeopleRank和PageRank有什么差别? 3.PR分析微博数据时,怎样对微博单个账号评分? 4.R语言怎样递归计算矩阵特征值? 5.怎样计算 ...

协同过滤(CF)算法

1 集体智慧和协同过滤 1.1 什么是集体智慧(社会计算)? 集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的,只是在 Web2.0 时代,大家在 Web ...

随机推荐

Objective－C( Foundation框架 一 NSFileManager)

NSFileManager 用来管理文件系统的 它可以用于常见的文件,文件夹操作(拷贝,剪切,创建) NSFileManager使用了单例模式(Singleton) 使用defaultManager可 ...

unity awake start 的区别

void Awake (){ } //初始化函数,在游戏开始时系统自动调用.一般用来创建变量之类的东西. void Start(){ } //初始化函数,在所有Awake函数运行完之后(一般是这样,但 ...

SQL UNION 操作符

转由http://www.w3school.com.cn/sql/sql_union.asp 这个网址的数据库知识,个人推荐,因为有实例,理解更透彻一些.非广告啊,个人感觉好啊 SQL UNION 操 ...

vector::erase returns incompatible iterator in debug build

关于std::vector中erase的用法http://www.cplusplus.com/reference/vector/vector/erase/ #include

poj2459 Treasure Exploration (闭包+二分)

这道题是让求派出机器人的最少数量,乍一看以为是简单的求最小路径覆盖,后来发现错了,因为有的点可以走多次,而二分中每个点只能走一次,所以要先用floyd进行传递闭包,然后用二分 #include< ...

Python每日一练(2):找出html中的所有链接(Xpath、正则两个版本)

要在hrml文件中找出特定的内容,首先需要观察该内容是什么东西,在什么位置,这样才能找出来. 假设html的文件名称是:"1.html".href属性全都在a标签里. 正则版: # ...

页面滚动图片等元素动态加载插件jquery.scrollLoading.js

如果一个网页很长,那么该页面的加载时间也会相应的较长.而这里给大家介绍的这个jQuery插件scrollLoading的作用则是,对页面元素进行动态加载,通俗的说就是滚到哪就加载到哪,屏幕以下看不见的 ...

解析ArcGis的字段计算器(一)——数值型数据计算，从“面积计算”开始

先来点儿背景知识铺垫: ArcMap的字段计算器提供了两种脚本语言的支持用以计算,两种脚本语言是VBScript与Python. 多数人选择使用前者,因为它的基本函数和Excel的函数貌似一样.注意我 ...

Codeforces Round #543 (Div. 2)B,C

https://codeforces.com/contest/1121 B 题意 给你n(<=1000)个数ai,找出最多对和相等的数,每个数只能用一次,且每个数保证各不相同 题解 重点:每个数 ...

Postman&#160;Postman测试接口之POST提交本地文件数据

Postman测试接口之POST提交本地文件数据   by:授客 QQ:1033553122 本文主要是针对用Postman POST提交本地文件数据的方法做个简单介绍 举例: 文件同步接口 接口地址 ...