社区发现
- 这有一篇有趣的比如解说什么是风控，还有一篇讲风控的运用——怎么经过校园卡消费记载识别情侣、基友、渣男和狗
- 什么是社区发现（Community Detection），简单说便是在一个联系网络（带权无向图）中找到潜在的特定安排结构，那些联系严密的安排往往具有明显的社群联系，发掘社群联系是社区发现的价值地点
- 作为风控的重要研讨对象，社区发现在交际、金融、心理、公安等各个领域开花成果，之前有幸主导过一个借助社区发现构建点评指标体系来预测某职业团伙发掘模型使用的规划开发，本文简要介绍下社区发现使用最广泛的Louvain算法的原理与实践
模块度
-
社区发现的最终方针便是对社区网络进行社团（community）或块（cluster）区分，社区/块内部联系越严密、外部联系越稀少（内紧外松）阐明算法作用越好
-
模块度（modularity）是最常用的度量办法
- 物理含义是社区内节点的连边数与随机情况下边数之差，取值规模[-0.5, 1)
- 模块度越挨近1，社团/块的区分作用越明显
-
社区发现算法门户许多，模块度是当下遍及认可的一种衡量标准，而Louvain便是依据模块度优化的启发式社区发现算法
Louvain
算法来源
-
Louvain算法出自比利时鲁汶大学Vincent D. Blondel教授等人2008年发表的论文Fast unfolding of communities in large networks，也称为Fast Unfolding算法，业界则直接取校名称号该算法
-
引证论文摘要先简单介绍下该算法：
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks.
-
大致意思是说：Louvain是一种能够快速提取大型网络中社区结构的算法。这是一种依据模块化优化的启发式办法，当时来说是被证明在一切社区发现算法中均匀时间复杂度最低的，用模块度衡量社区发现的质量也很好。不论是在比利时用260万用户通话数据上亿节点十几亿连接来做验证，仍是在ad-hoc网络上验证都是没问题的
算法原理
-
中心思想：遍历网络中一切相邻节点，将能够使模块度增量最大的节点（核算）归入到社团中，收敛后再对每个社团紧缩成单节点再次重复上述进程直至大局安稳，从而实现最大化全图的模块度
-
模块度核算：一般认为，全图模块度超越0.3就能发生比较好的区分作用
-
算法流程：
- 1.初始化，每个节点都是一个社团
- 2.模块化（Community Merging），每个节点依次将一切相邻节点兼并，核算模块度增益，存在则归入社团
- 3.重复步骤2，直至一切社团安稳
- 4.社团紧缩（Graph Reconstruction），将每个社团视为一个节点，重新核算社团内与社团间权重
- 5.再次模块化（Community Merging），直至紧缩后的社团安稳，算法完毕
-
算法优势：
- 1.核算复杂度低，收敛速度快
- 2.适用大型网络/图，尤其是稀少网络，可带权
- 3.安稳性与算法效率平衡较好
- 4.算法老练使用广泛，Python等言语均有安稳算法包可供直接调用
-
算法劣势：
- 1.不适用于稠密图，算法收敛慢
- 2.运用贪婪思想，简单发生过拟合，堕入部分最优
- 3.无权图或许不安稳，假如有多个最大增量为正且相同的社团可加入，假如随机选择加入会导致社团不同
-
算法演示：每一阶段都由两步组成，一是经过只允许社区的部分改变来优化社团，一是聚合找到的社团以树立一个新的社团；迭代地重复这些遍，直到不能再增加模块度停止
- 本人算法才能有限，大家能够看看通俗易懂的这篇原了解读
算法使用
-
Python调包侠，能够看看这个
-
保证算法的有用落地，得到一个还不错的模块度要做的作业不止算法实现与调优这么简单
实践与反思
-
个人举例，实践中经过中心成员选举进步社区网络准入门槛以及权重分配，小规模实验了多轮确定了较优的权重配比，上线后在一万节点，1.8万联系中跑出了0.5的模块度，经过人为抽样判断，得到了还算不错的团伙发掘作用
-
从成果来看还算不错，实践进程中仍是有东西值得进一步考虑的
- 1.事务模型头等重要，社区发现作为较老练的领域就不要寄过多期望于算法准确性提高，因为那是有限的，在项目工期有限的情况下依据团队才能选取开源、简单上手、安稳性不错的算法更重要，良好的事务模型也会得到解说性强的成果
- 2.领域知识（Domain Knowledge）是树立事务模型的前提，要深化了解也要重复确认，从数据科学和从传统事务解决问题的视点很有或许是截然不同的，但这部分是沟通的基础，也便是形成一致言语（Unique Language）
- 3.确定方针找到侧重点，同样是社区发现，更关注社团的规模安排，仍是更关注带有某些特性的社团联系，或许就会走上两条不同的模型构建之路，在茫茫然社群联系网中影响的是一整套模型使用的规划开发作业模式
