《数据科学导论》Graph模块：社区检测.pptx

Graph模块：社区检测社区检测（Community Detection）为什么使用图模型对数据建模？图提供了一种观察数据结构特征的视角一个空手道俱乐部中34个成员之间朋友关系形成的图你能发现什么特点？教练创始人最终这个俱乐分裂成两个对立的空手道俱乐部检测出图中的社区结构图片来源: [Easley and Kleinberg, Cambridge University Press, 2010]Node Centrality1. 弱连接理论（Weak Tie）2. Louvain社区发现算法3. 总结Graph模块真实网络中为什么能形成社区？果真如此吗？如果是真的话，为什么会是这样？在分析数据之前，首先要对数据的性质有足够的认识很多时候，我们认为真实网络（如社交网络）长这样Mark Granovetter的研究上世纪60年代末，Mark Granovetter在做他博士论文研究研究题目：人们是如何找到新的工作的发现1：人们通常是通过人际关系获取了新工作的信息发现2：获取新工作的人际关系通常是“点头之交”（casual acquaintances）而并非“亲密好友”（close friends）这个发现很让人惊讶一般认为，亲密好友对你的帮助应该大于点头之交的熟人。为什么？三元闭包（Triadic Closure）三元闭包（Triadic Closure）如果两个人在网络中有共同的好友，他们成为好友的几率也会提升几点原因：如果B和C都有共同的好友A，那么B更有可能遇到C——因为他们都与A有交集B和C更有可能互相信任——因为他们有共同的好友A更有可能介绍B和C认识三元闭包（Triadic Closure）量化指标：clustering coefficient节点A的clustering coefficient是A任意两个邻居是好友的概率?? 节点A的聚集因子 A. 1/2; B. 1/6 C. 1/3 D. 1/4clustering coefficient of A = 1/6 clustering coefficient of A = 1/2 [Bearman and Moody]青少年女孩调查：clustering coefficient越低越易自杀强关系 vs. 弱关系怎么解释下图中A和B之间的关系？强关系 vs. 弱关系Wildings怎么解释下图中A和B之间的关系？强关系 vs. 弱关系Granovetter从结构和社交功能两个角度将边分为强关系 Strong Tie弱关系 Weak Tie结构角度强关系意味着社交紧密弱关系链接网络不同部分社交功能角度弱关系让你从不同角度获取信息，从而找到新工作强关系在新信息获取方面的作用十分有限真实数据中的强弱关系[Onnela et al. 2007]测量了电话通信网络边的强弱表示打电话的次数Strong TieWeak Tie图片来源: [Onnela et al. 2007]Node Centrality1. 弱连接理论（Weak Tie）2. Louvain社区发现算法3. 总结Graph模块我们考虑一个小例子演示示例构造一个简单的社交网络思考如何自动地将右图中红色的点与黄色的点分开？def sample_community_graph (): G = nx.Graph() G.add_edges_from([(‘A’,‘B’), (‘A’,‘C’) , ('A','D'), ('B','C',),('B','D'), ('C','D'), ('B','E'), ('D','G'), ('E', 'G'), ('E','F'), ('F','G')]) return G问题定义?输入一个无向图输出一组点的划分 and 设计优化目标！给定图，评价的质量你会怎么定义？????优化目标：Modularity Q?给定图，度量一组划分 的质量基本想法度量划分的紧凑性????如何度量expected # edges within group s度量期望边数给定一个真实的图，包含个节点和条边为了度量任意两点之间期望的边数，构造一个图，使其满足与有着相同的点的度数分布，但点之间的连接是随机的可以是多重图（Multigraph）考虑任意两个点和，他们的度数为和，求它们之间期望的边数?节点和之间的期望边数 A. B. C. ??? ???度量期望边数?? A. 1 B. C. ?? ?给定一个真实的图，包含个节点和条边为了度量任意两点之间期望的边数，构造一个图，使其满足与有着相同的点的度数分布，但点之间的连接是随机的可以是多重图（Multigraph），边数为考虑任意两个点和，他们的度数为和，求它们之间期望的边数课堂练习：计算，并解释其含义优化目标：Modularity Q定义M