Community Detection 社群发现算法 - CSDN博客

标签: | 发表时间:2018-04-29 10:28 | 作者:
出处:https://blog.csdn.net

        社区发现(Community Detection)算法用来发现网络中的社区结构,也可以视为一种广义的 聚类算法。以下是我的一个 PPT 报告,分享给大家。



        从上述定义可以看出:社区是一个比较含糊的概念,只给出了一个定性的刻画。

另外需要注意的是,社区是一个子图,包含顶点和边。





        下面我们以新浪微博用户对应的网络图为例,来介绍相应的社区发现算法



        这里在相互关注的用户之间建立连接关系,主要是为了简化模型,此时对应的图为无向图。

当然,我们也可以采用单向关注来建边,此时将对应有向图。




        这个定义看起来很拗口,但通过层层推导,可以得到如下 (4.2)的数学表达式。定义中的随机网络也称为 Null Model,其构造方法为:

        the null model used has so far been a random graph with the same number of nodes, the same number of edges and the same degree distribution as in the original graph, but with links among nodes randomly placed.



       注意,(4.2) 是针对无向图的,因此这里的 m 表示无向边的条数,即若节点 i 和节点 j 有边相连,则节点 (i, j) 对 m 只贡献一条边




        标签传播算法(LPA)的做法比较简单:

第一步: 为所有节点指定一个唯一的标签;

第二步: 逐轮刷新所有节点的标签,直到达到收敛要求为止。对于每一轮刷新,节点标签刷新的规则如下:

        对于某一个节点,考察其所有邻居节点的标签,并进行统计,将出现个数最多的那个标签赋给当前节点。当个数最多的标签不唯一时,随机选一个。


注:算法中的记号 N_n^k 表示节点 n 的邻居中标签为 k 的所有节点构成的集合。



 


       SLPA 中引入了  Listener 和  Speaker 两个比较形象的概念,你可以这么来理解:在刷新节点标签的过程中,任意选取一个节点作为 listener,则其所有邻居节点就是它的 speaker 了,speaker 通常不止一个,一大群 speaker 在七嘴八舌时,listener 到底该听谁的呢?这时我们就需要制定一个规则。

        在 LPA 中,我们以出现次数最多的标签来做决断,其实这就是一种规则。只不过在 SLPA 框架里,规则的选取比较多罢了(可以由用户指定)。

        当然,与 LPA 相比,SLPA 最大的特点在于:它会记录每一个节点在刷新迭代过程中的 历史标签序列(例如迭代 T 次,则每个节点将保存一个长度为 T 的序列,如上图所示),当迭代停止后,对每一个节点历史标签序列中各(互异)标签出现的频率做统计,按照某一给定的阀值过滤掉那些出现频率小的标签,剩下的即为该节点的标签(通常有多个)。


SLPA 后来被作者改名为 GANXiS,且软件包仍在不断更新中......



        这里对上面的图做个简单介绍:带问号的节点是待确定标签的节点,黑色实心点为其邻居节点,它们的标签是已知的,注意标签均是由二元数对的序列构成的,序列中每一个元素的第一个分量表示其标签,第二个分量表示该节点属于该标签对应社区的可能性(或者说概率,叫做 belonging coefficent),因此对于每个节点,其概率之和等于 1。


        我们按照以下步骤来确定带问号节点的标签:


1. 获取邻居节点中所有的互异(distinct) 标签列表,并累加相应的 belonging coefficent 值。

2. 对 belonging coefficent 值列表做归一化,即将列表中每个标签的 belonging coefficent 值除以 C1 (C1 为列表中 belonging coefficent 值的最大值)。

3. 过滤。若列表中归一化后的 belonging coefficent 值(已经介于 0,1 之间)小于某一阀值 p (事先指定的参数),则将对应的二元组从列表中删除。

4. 再一次做归一化。由于过滤后,剩余列表中的各 belonging coefficent 值之和不一定等于 1,因此,需要将每个 belonging coefficent 值除以 C2 (C2 表示各 belonging coefficent 值之和)。


        经过上述四步,列表中的标签即确定为带问号节点的标签。




        这里,我们对 Fast Unfolding 算法做一个简要介绍,它分为以下两个阶段:


第一个阶段:首先将每个节点指定到唯一的一个社区,然后按顺序将节点在这些社区间进行移动。怎么移动呢?以上图中的节点 i 为例,它有三个邻居节点 j1, j2, j3,我们分别尝试将节点 i 移动到 j1, j2, j3 所在的社区,并计算相应的 modularity 变化值,哪个变化值最大就将节点 i 移动到相应的社区中去(当然,这里我们要求最大的 modularity 变化值要为正,如果变化值均为负,则节点 i 保持不动)。按照这个方法反复迭代,直到网络中任何节点的移动都不能再改善总的 modularity 值为止。


第二个阶段:将第一个阶段得到的社区视为新的“节点”(一个社区对应一个),重新构造子图,两个新“节点”之间边的权值为相应两个社区之间各边的权值的总和。


我们将上述两个阶段合起来称为一个 pass,显然,这个 pass  可以继续下去。


        从上述描述我们可以看出,这种算法包含了一种 hierarchy 结构,正如对一个学校的所有初中生进行聚合一样,首先我们可以将他们按照班级来聚合,进一步还可以在此基础上按照年级来聚合,两次聚合都可以看做是一个社区发现结果,就看你想要聚合到什么层次与程度。




        DCLP 算法是 LPA 的一个变种,它引入了一个参数来限制每一个标签的 传播范围,这样可有效控制 Monster (非常大的 community,远大于其他 community)的产生。



        


        最后,我们给出一些 实验结果

        对比上述两个表格可知:SDCLP 算法得到的 top 5 社区更为均匀。



       最近有很多朋友向我索要本文的 PPT,为方便大家参考,我把 本文的完整 PPTSPLA / GANXiS 软件包的源码以及 几篇相关算法的代表 Paper 打包了,有需要的读者请点击 社区发现算法资料自行下载。 


作者: peghoty 

出处:  http://blog.csdn.net/peghoty/article/details/9286905 

欢迎转载/分享, 但请务必声明文章出处.



相关 [community detection 社群] 推荐:

Community Detection 社群发现算法 - CSDN博客

- -
        社区发现(Community Detection)算法用来发现网络中的社区结构,也可以视为一种广义的. 以下是我的一个 PPT 报告,分享给大家.         从上述定义可以看出:社区是一个比较含糊的概念,只给出了一个定性的刻画. 另外需要注意的是,社区是一个子图,包含顶点和边.

电子书:The Art Of Community

- LiJunLe - Wow! Ubuntu
The Art Of Community 是由 Ubuntu Community Manager Jono Bacon 编写的一本关于如何构建开源社区的书籍. Jono Bacon 于 2006 年加入 Canonical,管理着世界范围内的 Ubuntu 开发者、贡献者及用户社区,有着丰富的开源社区运维经验.

使用JavaScript实现Motion Detection

- - Web App Trend
本篇文章作者 Romuald Quantin,他成为一个前端开发者已经13年有余,在过去的13年中,他一直尝试动画、视频等方面的开发. Romuald在音乐、艺术欣赏、声音设计和音乐方面都颇有造诣,这些使他在开发过程当中受益匪浅,下面我们就来看一下他是如何使用JavaScript实现Motion Detection的吧.

时间序列分段算法 [Time series Breakout Detection]

- - ITeye博客
在时间序列分析中,断点检测(breakout detection)是一个很基本的问题. 通过捕捉时序数据中的断点(breakout),来发现时序数据所表示的系统在过去是否发生了某种事件(event),进而为系统诊断提供必要的数据支持. 为了实现对时序断点的检测,我们首先需要对时序的整体时序做拟合. 这里我们通过一条直线来拟合一段时序,如果时序的趋势发生了变化,则用多条直线来拟合整条时序数据.

驚人的社群媒體行銷數據

- tinda - 數位時代 Beta3.0 | Topics & Links
數字會說話,盡管社群媒體的投資報酬率仍舊難以直接衡量,以下這些數字,卻可充分說明它的效用與潛力:. #廣告價格在今年上半年就增加了70%. #92%的社群網絡用戶都上Facebook. #分別有70%和66%的小型企業主,運用Facebook及Google來進行行銷. #如果有Facebook粉絲獨家銷售方案,11%的人都說他們會購買商品.

擁有社群媒體帳號,你,就是個媒體!

- daviddu - TechOrange
你擁有Facebook、Google+、Twitter或是Plurk帳號嗎. 只要有其中一個,而且你常在這些社交網站上更新自己的狀態,與朋友分享訊息,你就是個「媒體」. 計算一下,你在FB上有幾個朋友. 美國一份研究顯示,大部分的FB使用者的朋友名單中,有高達80%的人只是點頭之交,或者根本不認識.

我是免費資源網路社群,今年五歲!

- 勇 - 免費資源網路社群
今天是免費資源網路社群的「五歲」生日. 猶想起 2006 年八月十三日,我在 RegisterMore.com 註冊了我人生中第一個網域名稱,沒幾天後一個陽春簡易版的免費資源網路社群就此成形(八月十六日),當時會以 FreeGroup 作為網址、免費資源網路社群作為網站名稱純粹是為了 SEO,簡單來說就是希望在搜尋引擎中更容易被找到(至於是哪本書告訴我要這麼做,我也沒什麼印象了).

新聞媒體將死,社群網站當道?

- Cary - TechOrange
標題很聳動,但是當你想想:10 年前的今天,得知 911 恐怖攻擊事件的最快來源是:電視與平面媒體報導. 10 年後的 311 日本地震海嘯新聞,最快最多資訊的新聞來源是來自社群網站如 Twitter、噗浪、Facebook 等等社群網站,就不會這樣想了. 社群網站的訊息不一定最正確有深度,但最快最多,倒是難以令你我否認的.

Google+用分享社交圈創造社群行為新模式

- Jeshuang - TechOrange
Google+ 今天特別熱鬧,主要是開放了分享社交圈的功能. 顧名思義,就是讓你可以分享給朋友,你推薦的社交圈與相關朋友. 於是出現了正妹圈、宅男圈、科技圈、台灣圈、內地圈等五花八門的分享. 被分享到的人也有被一直圈的回應. 交叉圈選後的 Google+ 又做到了創新社群行為模式,不同於疲勞轟炸的 Facebook Ticker,也不同於安靜自 High 的 Twitter 訂閱.

《贏在社群網戰》導讀 — 射出不夠,還要成型

- iaotin - Mr. Jamie 看網路與創投
不,千萬別搞錯了,社群媒體並不是什麼了不起的新玩意兒. 事實上,自從有人類以來,它早就已經存在,比任何所謂的「傳統媒體」都還要傳統. 不,我應該要說它根本比人類還要傳統,連動物、甚至昆蟲其實都有社群媒體. 一切都只是名稱的問題罷了,還沒有 Facebook、Twitter 或是 Google+ 這些服務之前,這東西也曾叫做「病毒行銷」.