海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

http://blog.csdn.net/pipisorry/article/details/49052057海量数据挖掘MiningMassiveDatasets(MMDs)-JureLeskovec courses学习笔记之社交网络之社区检测:基本技巧-生成模型及其参数的梯度上升方法求解博客内容:社区检测的基本技巧部分,覆盖”overlappingcommunities”寻找最好集合

大家好,又见面了,我是你们的朋友全栈君。http://
blog.csdn.net/pipisorry/article/details/49052057

海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记之社交网络之社区检测:基本技巧-生成模型及其参数的梯度上升方法求解

博客内容:社区检测的基本技巧部分,覆盖”overlapping communities”寻找最好集合的机器学习技术。

Communities in Social Networks:  直觉上, 社区communities就是网络中个体的集合,集合中通常有高密度的边。而overlapping communities就是人们通常属于多个社区,如高中朋友、同事等等。

Note: lz这里这种方法是要自己指定社区个数的,有点类似软分类,通过MLE求解。

How the class fits together

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

图中社区检测

通过蛋白质连接结构发现细胞中的功能模块               社交网络(facebook)中的社区发现

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」        海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

社区类型

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

社区表示

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

我们可以将社交网络表示成一个graph adjacency matrix:有联系就有值,没有联系就没有值。矩阵中the thicker the tiles,the more edges are there in the network.我们要做的就是从networks中将这些tiles分离开来。

皮皮blog

网络生成模型Generative Model for Networks

网络模型

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

模型会有很多参数,通过估计这些参数,就可以隐含地检测出这些社区。

皮皮blog

社区隶属关系图模型AGM(community-affiliation graph model)

模型表示 B(V, C, M, {Pc})

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

模型中的边M代表成员-社区隶属关系。

AGM模型假定指定社区中的每个成员V(圆点)属于其对应社区C(方块)的概率是一样的,即Pc。

AGM生成Networks边的过程

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」 海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

用户u,v在网络中有边的概率P(u,v)就是其至少同属于一个社区的概率,共同社区越多,其概率值越大,概率越大越可能生成边。

Note: AGM模型中假定个体属于社区是没有权重的,或者说权重都为1。

AGM模型的优势

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」
皮皮blog

BIGCLAM模型

{AGM的relaxed版本。简化AGM成BIGCLAM,可以在large networks中检测社区}

带权值Memberships的AGM模型

对原始AGM模型进行relax,即考虑边权,重新计算两个个体属于同一社区A的概率P C(u, v)。

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

1. 原来成员u属于社区A是01表示,现在表示成一个绳strands,值越高,说明这个个体在社区中越活跃。

2. 用户u,v同时属于某个社区如A的概率PA(u,v),直觉上,如果两个都与社区A强关联,则两者间的关系就越强。PA(u,v)计算公式的一个重要性质是,如果某个Fu=0,就是u完全不属于社区A,则u,v也是没关联的。

使用因子矩阵Factor Matrix F重新构造P(U, V)

矩阵F就是BIGCLAM模型的表示。

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

概率 P(u,v)的计算

两个个体u,v生成links的概率表示,即在网络中有边的概率或者是至少同时属于一个社区的概率 P(u,v)的计算:

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

只要估计出矩阵F就可以计算出P(u,v),就可以通过P(u,v)概率生成图中的边。而矩阵F就给出了社区,完成社区检测。

Note: 如果F仅仅是0-1矩阵,则上式P(u, v)计算就是原始AGM模型了。

解BigCLAM

{给定一个网络G(V,E)我们知道节点和边,要找到这个模型BIGLAM的表示,也就是找到矩阵F}

最大似然估计:使用已知事实数据network G(V, E)估计F矩阵

为了使networks图中存在边的两点其属于同一社区的概率P(u, v)较大,同时不存在边的两点其属于同一社区的概率P(u, v)较小。我们要做的就是最大化下式。

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

[参数估计:最大似然估计MLE]

BigCLAM解F版本一:梯度上升

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

1. 使用梯度方法的一个假设:认为函数some kind of convex, smooth shape.并且这里我们是要求最大值而不是最小值,所以会使用梯度上升而不是梯度下降。如果将p(u,v),1-p(u,v)互换应该就可以使用梯度下降了。
2. 这里求梯度是对给定的node进行的,对应F的一行向量Fu,对Fu求导应该等价于对Fu各分量分别求导再重组成向量。

3. 这个算法可能导致其中的strands FuC变成负值,每次迭代都要检测并修正。

算法的缺点

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

导致这个的原因:由于计算和式(梯度式中第二部分)要遍历给定节点的所有非邻节点,要遍历整个数据。

BigCLAM解F版本二:cache缓存加速

通过邻居neibor来迭代求解F矩阵。缓存F中所有行的向量行和,就是将F所有行加起来,通过下式的转换就不用每次遍历整个数据了,只需遍历一次缓存,每次遍历的只是邻居节点。

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

BigClam的伸缩性scalability

海量数据挖掘MMDS week3:社交网络之社区检测:基本技巧「建议收藏」

更多关于求解F的细节的论文

Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach by J. Yang, J. Leskovec. ACM International Conference on Web Search and Data Mining (WSDM), 2013.
Detecting Cohesive and 2-mode Communities in Directed and Undirected Networks by J. Yang, J. McAuley, J. Leskovec. ACM International Conference on Web Search and Data Mining (WSDM),2014.
Community Detection in Networks with Node Attributes by J. Yang,J. McAuley, J. Leskovec. IEEE International Conference On Data Mining (ICDM), 2013.

from:http://blog.csdn.net/pipisorry/article/details/49052057

ref: [Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering 2016]

论文:复杂网络重叠社区检测《Finding overlapping communities in multiplex networks》N Afsarmanesh, M Magnani [Uppsala University] (2016) 

Community detection in networks: A user guide》S Fortunato, D Hric [ Indiana University & Aalto University School of Science] (2016)

论文:(社交)网络影响基准度量方法《Benchmarking Measures of Network Influence》A Bramson, B Vandermarliere (2016)

社交网络数据挖掘的前沿技术

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/129180.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Kafka容错性测试

    Kafka容错性测试1.查看topic信息(“副本”是为该分区复制日志的节点列表,无论它们是引导者还是当前处于活动状态,“isr”是“同步”副本的集合。这是副本列表的子集,当前仍处于活动状态并追随领导者。)[hadoop@hadoop000tmp]$kafka-topics.sh–describe–zookeeperhadoop000:2181–topicmy-replicated-topi…

  • 如何理解Python 面向对象编程思想

    如何理解Python 面向对象编程思想Python面向对象编程思想:从四个方面来理解1.宽泛的面向对象的概念举例说明面向过程:做一件事情,从头到尾,每一个细节都要关注,重点在于过程面向对象:做一件事情,用对象去做,不关心细节和过程,万物皆对象

    2022年10月26日
  • python中绝对值的表达式

    python中绝对值的表达式abs(x)print(abs(23))#23print(abs(-45))#45

  • nginx转发https到http

    nginx转发https到http微信小程序和公众号,要求外链的页面或API必须使用https。https意味着需要证书,在测试阶段,很不方便,因此部署的测试站点都是http。于是尝试在现有的https站点中,用nginx转发请求到只有http的测试站点。方法众所周知,在nginx.conf中添加一个转发规则。 server{ listen80; server_name服务器IP; 。。。 } server{ listen443ssl; server

    2022年10月19日
  • TIME_WAIT过多的解决办法

    TIME_WAIT过多的解决办法执行主动关闭的那端经历了这个状态,并停留MSL(最长分节生命期)的2倍,即2MSL。TIME_WAIT存在的两个理由:1可靠的实现TCP全双工连接的终止2允许老的重复的分节在网络上的消逝第一个:如果客户端不维持TIME_WAIT状态,那么将响应给服务端一个RST,该分节被服务器解释成一个错误。如果TCP打算执行所有必要的工作以彻底终止某个连接上两个方向的数据流,那么必须正确的处…

  • HTML中的空格字符_dw空格代码怎么打

    HTML中的空格字符_dw空格代码怎么打在学习插入空格字符代码书写方法之前,我们要知道,html代码的空格字符,在浏览器中,总会被压缩为一个字符!也就是说,你在html文本中输入多个空格,但在浏览器中,只会保留显示一个字符,其余的都将被浏览器删除。再打个比如,你在html中输入了8个空格字符,如下图所示:在显示之前,浏览器会删除其余7个,而只保留一个空格字符,如下图所示:也就是说,无论你输入多少个空格字符,在浏览器中显示的永远和上图一样…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号