方 滨 兴 中 国 工 程 院 院 士 2014 年 6 月 2 日 1
1 2 3 问 题 背 景 和 意 义 科 学 问 题 及 挑 战 最 新 研 究 进 展 2
1 2 3 问 题 背 景 和 意 义 科 学 问 题 及 挑 战 最 新 研 究 进 展 3
社 交 网 络 : 一 种 在 信 息 网 络 上 由 社 会 个 体 集 合 及 个 体 之 间 的 连 接 关 系 构 成 的 社 会 性 结 构 根 据 欧 盟 的 Key areas in the public sector impact of social computing, 在 线 社 交 网 络 可 分 为 即 时 消 息 类 在 线 社 交 类 微 博 类 共 享 空 间 类 四 类 http://www.tno.nl/downloads/social_com puting_impact_220609_final_report.pdf 4
即 时 消 息 类 应 用 : 一 种 提 供 双 信 推 送 通 信 的 平 台, 如 MSN QQ AIM 飞 信 微 信 等 ; 在 线 社 交 类 应 用 : 一 种 提 供 双 信 在 线 社 交 关 系 的 平 台, 如 Facebook Google+ 人 人 网 开 心 网 QQ 空 间 等 ; 微 博 类 应 用 : 一 种 提 供 单 信 推 送 短 信 息 的 平 台, 如 Twitter 新 浪 微 博 腾 讯 微 博 网 易 微 博 搜 狐 微 博 等 ; 共 享 空 间 类 应 用 : 其 他 可 以 相 互 沟 通 的 单 信 在 线 Web2.0 应 用, 如 论 坛 博 客 视 频 分 享 社 会 书 签 在 线 购 物 等 5
2009 年 5 月 2009 年 7 月 2009 年 9 月 2009 年 11 月 2010 年 1 月 2010 年 3 月 2010 年 5 月 2010 年 7 月 2010 年 9 月 2010 年 11 月 2011 年 1 月 2011 年 3 月 2011 年 5 月 2011 年 7 月 2011 年 9 月 2011 年 11 月 2012 年 1 月 2012 年 3 月 2012 年 5 月 12 亿 9 亿 6 亿 3 亿 Facebook:12.8 亿 Twitter:8.83 亿 腾 讯 微 博 :5.7 亿 新 浪 微 博 :5.36 亿 Facebook 上 线 10 年, 已 拥 有 超 过 1 2.8 亿 的 用 户, 是 第 二 大 人 口 国 6
政 治 经 济 文 化 生 活 微 博 是 国 家 机 构 倾 听 群 众 呼 声 收 集 社 情 民 意 的 新 武 器 社 交 网 络 传 播 不 实 消 息, 加 剧 官 民 对 立, 煽 动 不 满 情 绪, 危 害 国 家 安 全 公 安 部 利 用 社 交 网 络 打 黑 除 害 城 管 打 人 谣 言 引 发 群 众 聚 集 7
政 治 经 济 文 化 生 活 利 用 社 交 网 络 进 行 寻 找 雇 主 / 雇 员 等 商 业 活 动 人 工 骗 术 和 技 术 手 段 相 结 合, 利 用 社 交 网 络 进 行 欺 诈 社 交 网 络 的 求 职 招 聘 功 能 通 过 微 信 传 播 的 骗 术 消 息 8
政 治 经 济 文 化 生 活 社 交 网 络 媒 体 是 塑 造 公 益 文 化 的 权 威 可 信 的 介 质 极 端 思 想 自 由 思 潮 通 过 社 交 网 络 广 泛 传 播, 冲 击 社 会 文 化 价 值 观 念 微 博 打 拐 俄 极 端 主 义 者 在 社 交 网 络 发 布 煽 动 种 族 仇 恨 歌 曲 被 捕 9
政 治 经 济 文 化 生 活 社 交 网 络 有 利 于 扩 大 朋 友 圈, 获 得 关 心 和 认 同 感 自 重 感 信 息 透 明 的 社 交 网 络 中 隐 私 信 息 易 被 滥 用, 破 坏 正 常 生 活 社 交 网 络 提 升 用 户 认 同 感 澳 洲 1/5 网 民 的 个 人 信 息 被 滥 用 10
1 2 3 问 题 背 景 和 意 义 科 学 问 题 及 挑 战 最 新 研 究 进 展 11
社 交 网 络 分 析 是 指 从 网 络 结 构 群 体 互 动 信 息 传 播 三 个 维 度, 基 于 信 息 学 数 学 社 会 学 管 理 学 心 理 学 等 多 学 科 的 融 合 理 论 和 方 法, 为 理 解 人 类 各 种 社 交 关 系 的 形 成 行 为 特 点 分 析 以 及 信 息 传 播 的 规 律 提 供 的 一 种 可 计 算 的 分 析 方 法 12
在 线 社 交 网 络 是 一 种 在 信 息 网 络 上 由 社 会 个 体 集 合 及 个 体 之 间 的 连 接 关 系 构 成 的 社 会 性 结 构, 包 含 关 系 结 构 网 络 群 体 与 网 络 信 息 三 个 要 素 要 素 一 : 关 系 结 构 13
在 线 社 交 网 络 是 一 种 在 信 息 网 络 上 由 社 会 个 体 集 合 及 个 体 之 间 的 连 接 关 系 构 成 的 社 会 性 结 构, 包 含 关 系 结 构 网 络 群 体 与 网 络 信 息 三 个 要 素 要 素 一 : 关 系 结 构 要 素 二 : 网 络 群 体 14
在 线 社 交 网 络 是 一 种 在 信 息 网 络 上 由 社 会 个 体 集 合 及 个 体 之 间 的 连 接 关 系 构 成 的 社 会 性 结 构, 包 含 关 系 结 构 网 络 群 体 与 网 络 信 息 三 个 要 素 要 素 一 : 关 系 结 构 要 素 二 : 网 络 群 体 要 素 三 : 网 络 信 息 15
社 交 网 络 的 结 构 的 特 点 节 点 海 量 性 结 构 复 杂 性 多 维 演 化 性 Facebook 在 全 球 拥 有 超 过 12.8 亿 的 活 跃 用 户 用 户 之 间 的 关 系 结 构 非 常 复 杂 新 浪 微 博 有 5.36 亿 用 户, 用 户 间 关 系 包 括 关 注 / 粉 丝, 提 及, 转 发 等 Twitter 中 一 个 讨 论 传 染 初 期 病 的 社 区 在 30 天 内 的 演 化 图 30 天 后 16
群 体 互 动 的 特 点 群 体 集 合 数 个 Twitter 用 户 发 布 虚 假 消 息, 引 发 大 批 农 民 工 逃 离 孟 买 班 加 罗 尔 和 金 奈 等 城 市 的 公 共 群 体 恐 慌 事 件 强 交 互 2012 年 2 月 27 日, 讨 论 bigdata 的 Twitter 用 户 组 成 的 社 区 交 互 关 系 包 括 提 及, 回 复 和 关 注 / 粉 丝 等 关 系 情 感 变 化 急 剧 人 们 在 一 天 中 的 早 餐 时 段 最 正 面 积 极, 午 餐 过 后, 人 们 的 心 情 逐 渐 跌 到 谷 底 ; 临 睡 之 前, 人 们 的 情 绪 又 开 始 急 剧 回 升 17
信 息 传 播 的 特 点 多 源 并 发 性 李 开 复 在 多 个 社 交 网 络 平 台 上 注 册 账 号, 然 后 从 多 个 平 台 上 并 发 发 布 信 息 相 互 影 响 性 荷 兰 皇 家 航 空 公 司 运 用 社 交 媒 体 营 销 传 播, 利 用 Twitter 用 户 之 间 的 相 互 影 响, 取 得 了 很 好 的 效 果 内 容 演 化 性 2011 年, 埃 及 革 命 中 穆 巴 拉 克 宣 布 下 台 时 一 个 小 时 内 Twitter 中 话 题 Jan25 的 传 播 演 化 示 意 图 18
结 构 行 为 传 播 19
结 构 行 为 传 播 针 对 社 交 网 络 节 点 海 量 结 构 复 杂 性 和 多 维 演 化 性 等 特 点, 研 究 社 交 网 络 建 模 方 法, 共 性 特 征 分 析 方 法, 以 及 社 交 网 络 ( 虚 拟 社 区 ) 的 发 现 方 法 及 其 演 化 规 律 针 对 社 交 网 络 中 群 体 交 互 强 实 时 影 响 力 动 态 演 化 等 特 性, 研 究 群 体 行 为 形 成 机 理 情 感 建 模 方 法 群 体 交 互 影 响 度 量, 网 络 群 体 的 产 生 发 展 消 亡 规 律 针 对 社 交 网 络 中 信 息 多 源 并 发 内 容 演 化 等 特 性 研 究 信 息 内 涵 的 表 示 方 法 传 播 能 量 度 量 方 法 信 息 传 播 规 律 与 演 化 机 理, 以 及 信 息 传 播 影 响 力 最 大 对 抗 策 略 20
结 构 1 社 交 网 络 结 构 特 征 分 析 及 建 模 社 交 网 络 结 构 分 析 与 建 模 是 所 有 分 析 的 基 础 相 关 技 术 行 为 二 部 图 模 型 有 向 图 模 型 传 播 小 世 界 现 象 WS 模 型 重 尾 分 布 特 性 BA 模 型 21
结 构 2 虚 拟 社 区 发 现 技 术 虚 拟 社 区 发 现 是 社 交 网 络 分 析 的 必 具 功 能 行 为 贪 心 算 法 相 关 技 术 概 率 模 型 虚 拟 社 区 静 态 计 算 发 现 算 法 传 播 派 系 算 法 标 签 传 播 虚 拟 社 区 动 态 计 算 发 现 算 法 22
结 构 3 虚 拟 社 区 演 化 分 析 技 术 虚 拟 社 区 具 有 动 态 演 化 性, 需 对 演 化 机 理 进 行 分 析 与 识 别 行 为 结 构 多 样 性 相 关 技 术 平 衡 性 演 化 虚 拟 社 区 演 化 算 法 传 播 同 质 社 区 识 别 稳 定 社 区 识 别 同 质 虚 拟 社 区 识 别 算 法 23
结 构 1 个 体 行 为 分 析 技 术 个 体 互 动 行 为 是 社 区 中 的 基 本 动 作, 需 对 其 进 行 建 模 行 为 评 论 转 发 @ 转 发 评 论 @ 相 关 技 术 感 知 有 用 性 使 用 态 度 使 用 意 愿 感 知 易 用 性 Davis 接 受 模 型 实 际 使 用 传 播 Bhattacherjee 期 望 确 认 模 型 24
结 构 2 个 体 情 感 分 析 技 术 社 交 网 络 中 每 个 人 情 感 状 态 不 同, 影 响 力 也 不 同 生 气 流 泪 相 关 技 术 行 为 最 大 熵 LDA 模 型 传 播 坏 笑 憨 笑 层 次 化 情 感 向 量 模 型 25
结 构 3 个 体 影 响 力 分 析 技 术 具 体 每 个 人 的 影 响 力 也 各 不 相 同 观 点 : 支 持 国 产 观 点 : 支 持 国 产 相 关 技 术 行 为 HITS 算 法 传 播 PageRank 算 法 26
结 构 4 群 体 聚 集 及 影 响 机 制 群 体 聚 集 及 对 个 体 的 影 响 力 如 何 表 示 与 计 算 观 点 : 抵 制 日 货 相 关 技 术 行 为 蚁 群 算 法 传 播 羊 群 效 应 模 型 27
结 构 1 信 息 检 索 技 术 如 何 在 复 杂 的 社 交 网 络 中 检 索 到 需 要 的 信 息? 相 关 技 术 行 为 传 播 时 间 先 验 算 法 共 同 分 解 模 型 微 博 语 言 模 型 MLE t MAP t 微 博 搜 索 算 法 正 则 化 模 型 n( d, t td ) = nc ( ) n( d, t td ) -1 nc ( ) - - 2 基 于 模 型 的 社 会 化 推 荐 算 法 28
结 构 2 信 息 传 播 规 律 社 交 网 络 中 信 息 是 如 何 传 播 的? 其 规 律 如 何? 相 关 技 术 行 为 线 性 阈 值 模 型 独 立 级 联 模 型 1. 原 子 核 式 爆 发 传 播 2. 烟 花 式 僵 尸 爆 发 传 播 基 于 网 络 结 构 的 传 播 模 型 传 播 3. 星 球 爆 发 式 传 播 4. 水 母 扩 散 式 传 播 信 息 竞 争 传 播 模 型 多 元 信 息 传 播 模 型 基 于 信 息 特 性 的 传 播 模 型 29
结 构 3 话 题 发 现 与 演 化 如 何 发 现 大 家 都 在 讨 论 的 热 点 话 题? 以 及 话 题 是 如 何 演 化 的? 相 关 技 术 行 为 # 马 航 失 联 # 昆 明 砍 人 向 量 空 间 模 型 词 项 关 系 图 算 法 话 题 发 现 算 法 传 播 # 越 南 反 华 # 对 越 反 击 战 # 越 战 老 兵 待 遇 主 题 模 型 话 题 演 化 相 邻 时 间 片 关 联 算 法 话 题 演 化 算 法 30
结 构 4 影 响 力 最 大 化 如 何 发 现 最 有 信 息 传 播 影 响 力 最 大 的 节 点 与 方 法? 相 关 技 术 行 为 传 播 懒 惰 前 向 算 法 线 性 阈 值 模 型 基 于 博 弈 的 影 响 力 最 大 化 算 法 混 合 贪 心 算 法 影 响 力 最 大 化 贪 心 算 法 路 径 启 发 式 算 法 影 响 力 最 大 化 启 发 式 算 法 影 响 力 最 大 化 问 题 延 伸 与 变 形 31
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 4. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 32
1 2 3 问 题 背 景 和 意 义 科 学 问 题 及 挑 战 最 新 研 究 进 展 33
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 4. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 34
研 究 工 作 新 进 展 结 构 基 于 加 权 相 干 邻 域 紧 密 度 (WCNP) 的 标 签 传 播 社 区 发 现 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 研 究 目 标 利 用 标 签 传 播 算 法 发 现 社 交 网 络 中 的 社 区 结 构, 提 高 社 区 发 现 算 法 的 稳 定 性 原 始 标 签 传 播 算 法 初 始 时, 每 个 节 点 赋 予 唯 一 的 标 签 节 点 的 标 签 向 相 邻 节 点 传 播, 出 现 频 次 最 多 的 标 签 占 优, 若 有 多 种 标 签 频 次 相 同, 则 随 机 选 择 一 个 迭 代 上 述 步 骤, 相 同 标 签 的 节 点 构 成 社 区 不 足 与 改 进 v1 v3 v1 v3 v2 v4 v2 v4 v6 v5 v6 v5 v7 v8 v7 v8 初 始 化 时 每 个 节 点 都 具 有 唯 一 标 签, 节 点 颜 色 代 表 节 点 所 具 有 的 标 签, 考 虑 对 节 点 4 的 标 签 进 行 随 机 更 新 节 点 4 选 择 节 点 5 的 标 签 作 为 自 己 的 更 新 标 签 随 机 的 更 新 过 程 导 致 算 法 结 果 稳 定 性 差 我 们 提 出 自 适 应 的 加 权 相 干 邻 域 紧 密 度 来 衡 量 两 个 节 点 在 同 一 社 区 的 可 能 性, 并 基 于 此 进 行 标 签 传 播, 提 高 社 区 发 现 的 稳 定 性 v1 v3 v1 v3 v2 v2 v6 v5 v6 v5 v7 v8 v7 v8 节 点 2,3,6,8 可 能 进 行 的 更 新 最 终 被 划 成 一 个 社 区 35
研 究 工 作 新 进 展 结 构 基 于 加 权 相 干 邻 域 紧 密 度 (WCNP) 的 标 签 传 播 社 区 发 现 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 第 一 步 : 定 义 加 权 相 干 邻 域 紧 密 度 (Weighted-CNP) 衡 量 网 络 中 两 个 节 点 的 相 似 度, 由 三 个 紧 密 度 加 权 得 到 : 直 接 紧 密 度 : 节 点 之 间 是 否 存 在 边 三 角 紧 密 度 : 节 点 之 间 的 共 同 邻 居 数 配 合 紧 密 度 : 邻 居 节 点 中, 直 接 相 连 的 节 点 形 成 的 边 的 数 目 第 二 步 : 根 据 三 个 紧 密 度 在 整 个 网 络 中 的 分 布 情 况 计 算 各 自 的 特 征 熵, 再 由 特 征 熵 计 算 每 种 紧 密 度 的 权 重 α 1, α 2, α 3, 三 个 权 重 的 比 值 为 三 个 特 征 熵 倒 数 的 比 值 第 三 步 : 通 过 三 种 紧 密 度 的 加 权 求 和 计 算 得 到 网 络 中 边 的 权, 并 在 此 基 础 上 使 用 原 始 标 签 传 播 算 法 发 现 社 区 边 权 重 = 节 点 V1 与 V2 之 间 存 在 边, 所 以 节 点 V1 和 V2 的 直 接 紧 密 度 为 1; 节 点 V1 与 V2 的 共 同 邻 居 为 A,B,C,D, 所 以 节 点 V1 与 V2 之 间 的 三 角 紧 密 度 为 4; 节 点 V1 与 V2 之 间 配 合 紧 密 度 为 3( 存 在 边 AC,BC,BD); α 1 直 接 紧 密 度 +α 2 三 角 紧 密 度 +α 3 配 合 紧 密 度 36
研 究 工 作 新 进 展 结 构 基 于 加 权 相 干 邻 域 紧 密 度 (WCNP) 的 标 签 传 播 社 区 发 现 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 第 一 步 : 定 义 加 权 相 干 邻 域 紧 密 度 (Weighted-CNP) 衡 量 网 络 中 两 个 节 点 的 相 似 度, 由 三 个 紧 密 度 加 权 得 到 : 直 接 紧 密 度 : 节 点 之 间 是 否 存 在 边 三 角 紧 密 度 : 节 点 之 间 的 共 同 邻 居 数 配 合 紧 密 度 : 邻 居 节 点 中, 直 接 相 连 的 节 点 形 成 的 边 的 数 目 v1 v3 2 2 v2 v6 2 3 2 1 2 3 2 v4 v5 2 v7 2 v8 三 个 紧 密 度 的 权 重 均 取 1 时, 计 算 直 接 相 邻 节 点 之 间 的 WCNP 值, 重 新 构 建 新 网 络 标 签 传 播 时, 考 虑 边 的 权, 对 节 点 4 进 行 更 新 第 二 步 : 根 据 三 个 紧 密 度 在 整 个 网 络 中 的 分 布 情 况 计 算 各 自 的 特 征 熵, 再 由 特 征 熵 计 算 每 种 紧 密 度 的 权 重 α 1, α 2, α 3, 三 个 权 重 的 比 值 为 三 个 特 征 熵 倒 数 的 比 值 v1 v3 2 2 v2 v6 2 3 2 1 2 3 2 v4 v5 2 v7 2 v8 v4 和 v5 之 间 边 的 权 为 1, 所 以 节 点 4 不 能 再 选 择 节 点 5 的 标 签 作 为 其 更 新 标 签, 只 能 从 节 点 2 和 节 点 3 中 随 机 选 择 第 三 步 : 通 过 三 种 紧 密 度 的 加 权 求 和 计 算 得 到 网 络 中 边 的 权, 并 在 此 基 础 上 使 用 原 始 标 签 传 播 算 法 发 现 社 区 v1 v3 2 2 v2 v6 2 3 2 1 2 3 2 v4 v5 2 v7 2 v8 多 次 迭 代 后 最 终 划 分 为 两 个 社 区 37
研究工作新进展 SCI 收录 结构 基于加权相干邻域紧密度(WCNP)的标签传播社区发现方法 研究动机 算法主要思想 实验与结果 数据集 已知社区划分的社交网络 人工合成网络 实验设置 比较算法 原始标签传播算法 三个紧密度权重均为1的WCNP标签传播算法 (LAP-CNP-1) 基于特征熵的WCNP标签传播算法 LAPCNP-E 不同混合度下 LAP-CNP-1算法与原 始标签传播算法在 社区发现准确率上 的比较 度量指标 NMI 标准化交互信息熵 值越大越好 模块度 模块度越大社区划分质量越好 实验结论 算法在人工合成网络和现实已知社区结 Lou, Hao, et al. "Detecting community structure using label propagation 构的网络上的实验 证明了方法能提高 with weighted coherent neighborhood propinquity." Physica A: Statistical 原始标签传播算法的稳定性 Mechanics and its Applications, 2013. 38
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 4. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 39
研 究 工 作 新 进 展 群 体 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 研 究 目 标 基 于 情 感 特 征 的 突 发 现 象, 快 速 有 效 挖 掘 在 线 微 博 数 据 流 中 的 突 发 事 件 已 有 的 研 究 抽 取 文 档 特 征 词, 分 析 特 征 词 随 时 间 变 化 轨 迹 检 测 突 发 现 象 具 有 相 同 突 发 轨 迹 的 特 征 词 进 行 聚 合, 形 成 突 发 事 件 不 足 与 改 进 微 博 文 本 长 度 短 产 生 速 度 快 数 据 噪 声 大, 检 测 突 发 特 征 需 要 大 量 时 间 微 博 中 用 户 表 达 方 式 的 多 样, 突 发 特 征 可 能 由 网 络 新 词 构 成, 增 加 突 发 特 征 识 别 的 难 度 通 过 监 测 微 博 数 据 流 中 的 情 感 态 势 变 化, 达 到 检 测 突 发 事 件 的 目 的 文 档 流 突 发 特 征 词 检 测 相 同 轨 迹 突 发 特 征 词 合 并 突 发 事 件 40
研 究 工 作 新 进 展 群 体 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 Step1. 基 于 层 次 化 情 感 向 量 模 型, 对 微 博 数 据 流 的 情 感 特 征 进 行 抽 取, 将 微 博 数 据 流 按 照 情 感 进 行 分 类 仅 保 留 含 有 情 感 信 息 的 微 博 Step2. 对 情 感 特 征 进 行 主 成 分 分 析, 选 取 主 流 情 感 进 行 突 发 特 征 检 测 采 用 Kleinberg 算 法 检 测 每 种 情 感 的 突 发 状 态 及 突 发 期 微 博 流 情 感 抽 取 情 感 模 型 突 发 情 感 检 测 主 成 分 分 析 突 发 检 测 惊 讶 悲 伤 恐 惧 提 取 得 到 每 个 突 发 情 感 下 的 微 博 文 档 集 合 惊 讶 : d 11, d 12, 悲 伤 : d 21, d 22, 恐 惧 : d 31, d 32, 41
研 究 工 作 新 进 展 群 体 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 Step1. 基 于 层 次 化 情 感 向 量 模 型, 对 微 博 数 据 流 的 情 感 特 征 进 行 抽 取, 将 微 博 数 据 流 按 照 情 感 进 行 分 类 仅 保 留 含 有 情 感 信 息 的 微 博 Step2. 对 情 感 特 征 进 行 主 成 分 分 析, 选 取 主 流 情 感 进 行 突 发 特 征 检 测 采 用 Kleinberg 算 法 检 测 每 种 情 感 的 突 发 状 态 及 突 发 期 Step3. 提 取 微 博 中 的 命 名 实 体, 并 以 命 名 实 体 为 主 要 特 征 对 每 种 情 感 的 突 发 期 内 的 微 博 进 行 聚 类, 发 现 突 发 事 件 Step4. 根 据 命 名 实 体 ( 时 间 地 点 人 物 ) 的 相 似 性, 将 多 个 情 感 中 的 突 发 事 件 进 行 合 并, 形 成 最 终 的 突 发 事 件 集 合 突 发 情 感 的 微 博 文 档 集 合 惊 讶 : d 11, d 12, 悲 伤 : d 21, d 22, 恐 惧 : d 31, d 32, 对 各 情 感 下 的 微 博 分 别 进 行 聚 类 发 现 突 发 事 件 惊 讶 : e 11, e 12, 悲 伤 : e 21, e 22, 恐 惧 : e 31, e 32, (d- 微 博,e- 事 件 ) 对 微 博 文 档 中 的 命 名 实 体 进 行 识 别 e 1 : d 11, d 12, e 2 : d 21, d 22, e 3 : d 31, d 32, 对 多 个 情 感 下 的 相 似 事 件 进 行 合 并 42
研究工作新进展 第30届中国数据库学术会议最佳论文 基于情感突发的在线突发事件检测模型 群体 研究动机 算法主要思想 数据集 新浪微博 数据来源 新浪微博 时间 2012年7月25日至8月12日 数量 3,923,641条 主题 伦敦奥运会 实验设置 滑动时间窗口T为1小时 最小时间刻度为1分钟 在每个时间窗口中分别选择top5 top10 top20个事件构成最终事件 集合 采用覆盖率和准确率衡量算法效果 实验与结果 280 100 覆盖数量 覆盖率 250 95 90 200 150 80 70 SinglePass Kleinberg Top5 Top10 Top20 与SinglePass算法及Kleinberg算法进行对 比 实验结论 Zhang, Lumin, et al. "Detecting real-time burst topics in microblog 最高算法覆盖率达到96.9%,平均准 streams: how sentiment can help." Proceedings of the 22nd international 确率为85% conference on World Wide Web companion. International World Wide 本文的算法可以快速有效的检测出微 博中的突发事件 Web Conferences Steering Committee, 2013. 43
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 4. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 44
研 究 工 作 新 进 展 群 体 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 研 究 目 标 设 计 一 种 基 于 多 关 系 网 络 的 影 响 力 评 估 方 法, 挖 掘 微 博 中 影 响 力 用 户 已 有 研 究 方 法 利 用 个 体 属 性 衡 量 影 响 力 粉 丝 数, 被 转 发 数, 被 回 复 数 基 于 单 一 网 络 关 系 的 随 机 游 走 模 型 不 足 与 改 进 PageRank TwitterRank 考 虑 话 题 相 似 度 与 博 文 数 目 已 有 研 究 忽 略 了 微 博 中 多 网 络 关 系 特 性 我 们 给 出 了 微 博 中 多 关 系 计 算 方 法, 提 出 了 基 于 多 关 系 网 络 的 确 定 统 计 与 随 机 游 走 相 结 合 的 模 型 45
研 究 工 作 新 进 展 群 体 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 算 法 步 骤 第 一 步 : 基 于 主 题 模 型 的 话 题 抽 取 第 二 步 : 利 用 显 示 标 签 提 取 回 复 关 系 与 转 发 关 系 第 三 步 : 基 于 博 文 相 似 性 与 时 间 差 分 布 函 数 推 断 复 制 关 系 概 率 复 制 关 系 : 隐 含 转 发 关 系, 不 规 范 使 用 RT @ 标 签 或 直 接 复 制 原 博 文 第 四 步 : 基 于 个 人 兴 趣 相 似 性 与 发 帖 时 序 模 式 推 断 阅 读 关 系 概 率 阅 读 关 系 : 隐 含 关 注 关 系, 用 户 阅 读 关 注 好 友 博 文 的 概 率 第 五 步 : 多 关 系 网 络 确 定 统 计 与 随 机 游 走 相 结 合 模 型 个 体 在 单 一 网 络 中 确 定 路 径 或 随 机 游 走 融 合 多 关 系 网 络 计 算 整 体 影 响 力 举 例 : 多 关 系 网 络 游 走 游 走 游 走 Topic1 Topic2 游 走 Topic0 转 发 游 走 随 机 游 走 阅 读 回 复 回 复 随 机 游 走 复 制 随 机 游 走 随 机 游 走 Topic3 Topic4 回 复 网 络 转 发 网 络 复 制 网 络 阅 读 网 络 加 权 融 合 多 关 系 网 络 影 响 力 个 体 随 机 游 走 46
研 究 工 作 新 进 展 SCI 收 录 群 体 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 数 据 集 实 验 获 取 Twitter 中 2011-04-15 到 2011-07-15 三 个 月 之 间 的 中 文 用 户 及 博 文 用 户 数 目 :261,954 博 文 数 目 :2,660,281 实 验 设 置 结 论 实 验 对 比 了 微 博 中 其 他 5 种 常 用 个 体 影 响 力 衡 量 方 法, 验 证 了 各 算 法 在 影 响 力 个 体 挖 掘 中 的 准 确 率 召 回 率 F 值 5 种 常 用 个 体 影 响 力 衡 量 方 法 :TwitterRank, 转 发 网 络, 回 复 网 络, 粉 丝 数 目, 发 帖 数 目 我 们 提 出 的 基 于 多 关 系 网 络 的 影 响 力 个 体 挖 掘 方 法 整 体 性 能 最 优, 实 验 结 果 具 有 更 好 的 准 确 率 召 回 率 和 F 值 其 次 为 TwitterRank 算 法 和 仅 依 靠 转 发 网 络 衡 量 个 体 影 响 力 依 靠 回 复 网 络 粉 丝 数 目 和 发 帖 数 目 衡 量 个 体 影 响 力 实 验 效 果 最 差 0.8 0.6 0.4 0.2 F The average F measure of all topics RepostRank ReplyRank FollowerNum TweetNum TwitterRank MultiRank1 MultiRank2 我 们 的 方 法 : 图 中 最 上 方 三 条 曲 线, 效 果 最 优 MultiRank3 0 top10 top20 top50 top100 top200 top500 Zhaoyun, Ding, et al. "Mining topical influencers based on the multirelational network in micro-blogging sites." Communications, 2x 正 确 率 x China 召 回 率 10.1 F= (2013): 93-104. 正 确 率 + 召 回 率 47
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 4. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 48
研 究 工 作 新 进 展 信 息 微 博 流 行 度 预 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 研 究 目 标 设 计 一 种 微 博 的 流 行 度 预 测 方 法 通 过 观 测 一 篇 微 博 发 布 后 的 早 期 特 征 预 测 其 在 未 来 能 否 变 得 热 门 已 有 的 研 究 从 微 博 固 有 特 征 入 手 从 微 博 早 期 传 播 特 征 入 手 本 文 的 工 作 本 文 聚 焦 于 微 博 的 早 期 转 发 者 所 处 的 网 络 结 构 对 微 博 流 行 度 的 影 响 微 博 转 发 图 微 博 微 博 固 有 特 征 微 博 内 容 微 博 发 表 时 机 是 否 意 见 领 袖 微 博 早 期 传 播 特 征 早 期 流 行 度 本 文 的 工 作 早 期 连 接 密 度 早 期 传 播 深 度 相 关 术 语 解 释 : 微 博 流 行 度 : 微 博 的 转 发 次 数 连 接 密 度 : 转 发 微 博 的 用 户 间 有 多 少 关 注 关 系 传 播 深 度 : 微 博 转 发 链 的 最 大 长 度 49
研 究 工 作 新 进 展 信 息 微 博 流 行 度 预 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 Step1. 观 察 了 微 博 发 表 后 1 小 时 内 的 连 接 密 度 与 传 播 深 度 与 该 微 博 最 终 流 行 度 的 关 系 观 察 结 果 显 示 : 早 期 连 接 密 度 越 低 早 期 传 播 深 度 越 高 微 博 越 容 易 流 行 Step2. 对 微 博 的 早 期 流 行 度 与 上 述 两 个 观 测 量 的 对 数 进 行 加 权 求 和, 构 造 微 博 最 终 流 行 度 的 预 测 模 型, 并 通 过 微 博 数 据 训 练 模 型 参 数 早 期 连 接 密 度 与 最 终 流 行 度 的 关 系 log - log 早 期 传 播 深 度 与 最 终 流 行 度 (log) 的 关 系 ln p k t r = α 1 ln p k t i + α 2 ln ρ k (t i ) + α 3 ln p k t r = β 1 ln p k t i β 2 d k (t i ) + β 3 微 博 的 最 终 流 行 度 微 博 的 最 终 流 行 度 微 博 的 早 期 流 行 度 早 期 传 播 深 度 = α 1 +α 2 +α 3 微 博 的 早 早 期 连 期 流 行 度 接 密 度 ( 权 值 α 1, α 2, α 3, β 1, β 2, β 3 R) = β 1 β 2 +β 3 50
研 究 工 作 新 进 展 WWW2013 论 文 信 息 微 博 流 行 度 预 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 实 验 设 置 : 数 据 集 : 新 浪 微 博 (WISE2012 Challenge) 原 帖 时 间 :2011 年 7 月 1 日 ~7 月 31 日 转 发 时 间 :2011 年 7 月 1 日 ~8 月 31 日 微 博 总 数 :1660 万 使 用 其 中 75% 的 数 据 作 为 训 练 集 剩 下 的 25% 作 为 测 试 集 实 验 结 论 实 验 证 明 微 博 早 期 传 播 的 结 构 特 征 能 够 影 响 到 微 博 最 终 的 流 行 度 具 有 较 低 的 连 接 密 度 和 较 高 的 传 播 深 度 的 微 博 有 更 大 的 流 行 趋 势 Baseline: 仅 考 虑 早 期 流 行 度 With link density: 早 期 流 行 度 - 连 接 密 度 With diffu. Depth: 早 期 流 行 度 + 传 播 深 度 评 价 指 标 : RMSE: 均 方 根 误 差 MAE: 平 均 绝 对 误 差 Bao, Peng, et al. "Popularity prediction in microblogging network: a case study on sina weibo." Proceedings of the 22nd international conference on World Wide Web companion. International World Wide Web Conferences Steering Committee, 2013. 51
结 构 1. 基 于 加 权 相 干 邻 域 紧 密 度 的 标 签 传 播 社 区 发 现 方 法 2. 基 于 种 子 扩 展 的 局 部 社 区 发 现 方 法 行 为 传 播 3. 在 线 社 会 网 络 用 户 行 为 驱 动 力 及 模 型 研 究 4. 基 于 情 感 突 发 的 在 线 突 发 事 件 检 测 模 型 5. 微 博 中 基 于 多 关 系 网 络 的 话 题 层 次 影 响 力 个 体 挖 掘 方 法 6. 微 博 流 行 度 预 测 方 法 7. 微 博 中 结 合 时 间 与 网 络 位 置 的 个 体 传 播 能 力 分 析 方 法 8. 基 于 个 体 知 识 的 微 博 流 事 件 检 测 方 法 9. 基 于 异 构 并 行 计 算 框 架 的 影 响 最 大 化 加 速 算 法 52
研 究 工 作 新 进 展 信 息 基 于 个 体 知 识 的 微 博 流 新 事 件 检 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 研 究 目 标 设 计 一 种 在 线 无 监 督 的 方 法 从 微 博 流 中 检 测 出 现 实 中 可 能 发 生 的 新 事 件 已 有 的 研 究 检 测 既 有 的 新 闻 报 道 与 待 处 理 文 档 间 的 特 征 相 似 度 差 异 发 现 新 事 件 不 足 与 改 进 语 义 特 征 时 序 特 征 等 经 典 方 法 : Singlepass(Singlelink) 这 一 方 法 不 适 用 于 特 征 稀 缺 的 微 博 短 文 本 考 虑 微 博 中 的 富 交 互 特 征, 为 每 一 个 用 户 建 立 一 个 判 别 新 事 件 的 Singlepass 模 型, 利 用 群 体 智 慧 解 决 问 题 待 检 测 文 档 与 现 有 事 件 模 型 一 一 比 较 与 既 有 模 型 均 不 相 似 发 现 新 事 件! 既 有 事 件 A 既 有 事 件 B 既 有 事 件 C 53
研 究 工 作 新 进 展 信 息 基 于 个 体 知 识 的 微 博 流 新 事 件 检 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 Step1. 用 关 键 词 从 微 博 流 中 收 集 相 同 话 题 的 文 档, 抽 取 其 中 全 部 作 者 构 成 微 博 用 户 集 合, 找 出 作 者 关 联 信 息, 和 作 者 间 关 注 关 系 Step2. 还 原 微 博 转 发 / 评 论 结 构, 形 成 树 状 结 构 Step3. 以 每 个 用 户 为 单 位 建 立 新 事 件 评 判 模 型, 用 户 自 撰 的 微 博, 关 注 的 微 博 和 参 与 过 的 微 博 构 成 了 用 户 知 识 模 型 用 户 依 据 自 己 的 模 型 可 以 对 新 事 件 进 行 判 定 判 定 过 程 与 SinglePass 相 似 Step4. 对 于 在 线 微 博 流 中 的 每 篇 文 档, 调 用 各 个 用 户 的 评 判 模 型 对 其 进 行 投 票 采 用 近 似 的 一 票 否 决 制, 只 要 有 少 量 用 户 认 为 此 事 件 曾 经 出 现 过, 则 不 是 一 个 新 事 件 Step5. 用 户 模 型 的 更 新 转 发 投 票 结 论 User 1 User 2 User 3 User 4 转 发 微 博 传 播 关 系 User 1 自 撰 的 微 博 关 注 的 微 博 参 与 的 微 博 不 见 确 过 信 关 注 新 微 博 训 练 模 型 转 发 User 2 User 3 User 4 自 撰 的 微 博 关 注 的 微 博 参 与 的 微 博 自 撰 的 微 博 关 注 的 微 博 参 与 的 微 博 我 以 前 见 过 这 个 的 内 容 吗? 不 没 确 见 信 过 转 发 没 见 过 互 粉 这 这 不 是 一 个 新 事 件 转 发 自 撰 的 微 博 关 注 的 微 博 参 与 的 微 博 没 见 过 时 间 t 转 发 微 博 流 不 同 颜 色 = 不 同 用 户 发 帖 用 户 判 别 模 型 54
研 究 工 作 新 进 展 EI 收 录 信 息 基 于 个 体 知 识 的 微 博 流 新 事 件 检 测 方 法 研 究 动 机 算 法 主 要 思 想 实 验 与 结 果 数 据 集 : 新 浪 微 博 关 于 日 本 311 大 地 震 的 微 博 采 集 日 期 从 3.11~3.20, 持 续 十 天, 预 处 理 后 共 计 58 万 余 条 微 博 实 验 设 置 : 与 在 线 新 事 件 检 测 中 常 用 的 Singlepass 聚 类 方 法 进 行 对 比 人 工 对 新 事 件 准 确 与 否 进 行 评 价 实 验 结 论 对 检 出 的 事 件 按 簇 进 行 评 价, 以 小 时 为 粒 度 参 阅 wikipedia 日 本 气 象 厅 官 网, 和 各 门 户 网 站 当 时 的 报 道 本 方 法 比 传 统 检 出 新 事 件 准 确 率 更 高 能 检 测 出 一 定 程 度 上 语 义 相 似 的 事 件 检 出 的 新 事 件 ( 簇 ) 的 数 量 Singlepass 45 18 本 方 法 检 出 准 确 率 24.4% 66.7% 检 出 的 新 事 件 分 布 情 况 检 出 的 新 事 件 描 述 主 要 分 布 在 时 间 线 前 端 检 测 到 了 主 震, 和 抢 盐 等 事 件, 时 间 线 前 端 分 布 大 量 误 判 分 布 较 均 匀 检 测 到 了 主 震 大 部 分 高 震 级 的 余 震 和 中 国 大 陆 地 区 抢 盐 等 事 件 55
我 们 的 社 交 网 络 分 析 开 源 社 区 ( Socialysis.org ) 目 前 已 有 70 多 家 国 内 外 的 顶 级 科 研 单 位 注 册, 有 1300 多 名 知 名 专 家 学 者 会 员 实 名 注 册 开 源 社 区 组 织 大 陆 分 部 北 美 分 部 港 澳 分 部 澳 洲 分 部 56
973 项 目 社 交 网 络 分 析 与 网 络 信 息 传 播 的 基 础 研 究 北 京 邮 电 大 学 中 科 院 计 算 所 北 京 理 工 大 学 北 京 大 学 国 防 科 技 大 学 上 海 交 通 大 学 北 京 科 技 大 学 合 肥 工 业 大 学 57