6社区发现算法工作简介by@sumnoust.pdf

社区发现算法⼯作简介 - 机器学习算法班 @sumnous_t 2014.12.14 主要内容 • 社区发现算法的发展、简介 • 我的社区发现算法相关⼯作 Web 1.0 Web 2.0 Web 3.0 • ⺴络的社交与信息连接度 We Web Web b Web WWW-以信息为中⼼ Social Web-以⼈为中⼼ Semantic Web-让机器去理解⺴络上⼀切数据、信息、内容的含义。 • 研究背景与研究意义 • 研究背景： 复杂⺴络是复杂系统的抽象，现实中许多复杂系统都可以⽤复杂⺴络的相关特性进⾏ 描述和分析。 图，⺴络中的节点表⽰系统中的个体，边表⽰个体之间的关系。 如，社会关系⺴络，万维⺴，⾷物链，基因⺴，城市交通⺴络，电⼒⺴，电路⺴。 对复杂⺴络的研究⼀直是许多领域的研究热点，其中社区结构是复杂⺴络中得⼀个普 遍特征，整个⺴络是由许多个社区组成的。 • 研究意义： 社区发现: 更准确的定位社会群体，以便⽤于⼲告的精准投放，推荐商品，推荐好友，等等。 异构⺴络社区发现: 如在学术⺴络中依据指定研究主题寻找权威作者、在商务⺴络中针对特定产品查找营 销群体等，还可以在复杂的学术⺴络中划分出关系紧密的作者群体，在多种⼈际关系 中分析出志同道合的朋友圈等。 ⼩世界⺴络 Small World • 1998，邓肯·⽡茨（Duncan Watts）和斯蒂⽂·斯特罗加茨 （Steven Strogatz），⽡茨-斯特罗加茨模型（WS模型） • 特征路径⻓度短（两个节点的路径⻓度的平均值） • ⾼集聚系数（⼀个节点的集聚系数等于与它相连的节点中相 互连接的点对数与总点对数的⽐值） • 六度分割理论，⼀百五⼗法则 • 凯⽂⻉肯游戏（平均的“⻉肯数”是2.981 ，最⼤的也仅仅是 8） • Facebook六度分隔理论变为「四度」 （4.74 ，7.21亿） ⽆标度⺴络 Scale-free • ⼀个⺴络的度分布，是当随机地从⺴络中抽取⼀个 节点时，与这个节点相连的节点数（叫做这个节点 的度）d 的概率分布。 • ⽆尺度⺴络的度分布满⾜幂律分布，也就是说d =