算法入门

社交网络分析

中级

大约 4 个月

6小时每周 (按照自己的节奏)

加入成千上万的全球学员

开始免费课程

加入课程
免费
可享受
课程视频
实战练习
中级

大约 4 个月

6小时每周 (按照自己的节奏)

加入成千上万的全球学员
观看算法入门课程介绍
观看视频

课程概述

你玩过 Kevin Bacon 游戏吗?此课程将通过介绍算法的设计与分析,揭秘个体在社交网络中连接的方式,向你展示该游戏的原理。

为什么学习这门课程?

学完本课程后,你将了解为图形和其他重要的数据结构设计新算法,以及评估这些算法的效率所需的关键概念。

先修要求

此课程要求学习者了解 CS101 计算机科学导论同等级别的编程知识,包括能够用 Python 编写短小的程序;并能熟练运用高中代数 II 或 SAT 级别的数学符号。

查看使用优达学城的技术要求

学习计划

第 1 课:社交网络魔术

目标:熟悉算法分析

  • 欧拉路径
  • 朴素贝叶斯算法的正确性
  • 俄国农夫算法
  • 测量时间
  • 朴素贝叶斯算法和俄国农夫算法的步骤
  • 分治算法

第 2 课:社交网络的增长率

目标:使用数学工具来分析事物连接的方式。

  • 链状、环型和网格网络
  • Big Theta 算法度量
  • 平面图
  • 节点、边、区域
  • 平面图中边的增长率
  • 超立方体
  • 随机生成的图
  • N 的平方
  • 复杂的超立方体

第 3 课:基本图形算法

目标:找到通往 Kevin Bacon 的最快路径。

  • 社会网络的属性
  • 聚类系数
  • 连接的部分
  • 连接部分的运行时间
  • 检查成对连接性
  • 成对最短路径
  • 深度与广度优先搜索
  • 递归替换
  • Marvel 游戏“社交”网络
  • 寻找“桥边”

第 4 课:找到你认识的人

目标:使用堆追踪你最好的朋友

  • 程度中心性
  • 通过分割算法获得 Top-K
  • 三个分割案例
  • 堆的属性
  • 拼凑堆
  • 向下建堆
  • 堆排序

第 5 课:强和弱的连接

目标:使用具有边权重的社交网络

  • 构建树
  • 联系的强度
  • 加权社交网络
  • 如何找到最短路径
  • Dijkstra 的最短路径算法
  • Floyd-Warshall 算法简介
  • 随机化聚类系数
  • 估计的边界

第 6 课:网络问题的硬度

目标:探索某个社交网络问题比其他问题“更硬”是什么意思。

  • 瞬态事务异常报告系统 (TRISTAN)
  • 指数运行时间
  • 硬度
  • 降低硬度:长路径和简单路径
  • 多项式时间可判定问题
  • 非确定性多项式时间可判定问题
  • NP 问题中的分团问题
  • 寻找陌生人
  • 图着色是 NP-完全问题

第 7 课:回顾和应用

  • 采访达特茅斯学院教授 Peter Winker,话题为“名称和框问题以及智力测验和算法”
  • 采访罗格斯大学教授 Tina Eliassi-Rad,话题为“网络和社交网络中安全与反抗的统计方法”
  • 采访微软研究员首席研究员 Andrew Goldberg,话题为“实用算法”
  • 采访罗格斯大学研究生 Vukosi Marivate,话题为“社交网络算法”
  • 采访微软首席研究员 Duncan Watts,话题为“可以使用两个节点的路径”
  • 图形搜索动画简介

讲师与合作伙伴

Michael Littman

Michael Littman

Michael Littman 是布朗大学计算机科学教授。他也讲授优达学城在处理社交网络的算法课程(CS215)。在2012年加入布朗大学之前,他于2009年-2012年期间担任罗格斯大学计算机科学系主任,领导了罗格斯实验室实际强化学习(RL3)项目。他是美国人工智能协会 (AAAI) 研究员,曾担任 AAAI 2013年会议及2009年机器学习国际会议的程序主席,并获得了杜克大学和罗格斯大学的校级教学奖。Charles Isbell 曾教授他对回力网球、举重和极限飞盘,但是他并不擅长其中的任何一项。不过他却非常擅长歌唱和杂技。

官方微信公众号二维码

优达学城(Udacity)微信