5-数据挖掘概论

两大派别

  • 计算机科学家
    • 认为机器学习是人工智能的一个重要分支，机器学习作为实现人工智能的一个重要途径
  • 统计学家
    • 往往认为机器学习就是统计学习，是统计学中偏向应用的一个分支，对统计学习之外的手段（基于代数的、逻辑的、几何的学习等）会比较排斥

三大流派

  • 符号主义
    • 又称逻辑主义、心理学派或计算机学，其原理主要为物理符号系统（即符号操作系统）假设和有限性原理。符号主义者最早在1956年首先提出了“人工智能”术语，又发展了启发式算法-专家系统-知识工程理论与技术，并在20世纪80年代取得很大发展，代表人物纽厄尔、西蒙等。
  • 连接主义（联结主义）
    • 又称为结构主义、仿生学派或生理学派，主要原理为神经网络及神经网络间的连接机制与学习算法。代表性成果是1943年由生理学家麦卡洛克和数理逻辑学家皮茨创立的脑模型，60-70年代出现的以感知机为代表的脑模型研究，1986年鲁梅哈特等人提出多层网络中的反向传播算法（BP）。
  • 行为主义
    • 又称为进化主义或控制论学派，其原理为控制论即感知-动作型控制系统。控制论把神经网络系统的工作原理与信息理论、控制理论、逻辑以及计算机联系起来。

数据与特征

  • 数据的结构与表示
    • 非结构化数据：文档、图片、音频、视频
    • 半结构化数据：HTML, HTML5, XML, RDF、图、树
    • RDF（资源描述框架）：SPO（subject，predicate，object）三元组，RDF 是知识图谱常用的存储格式
    • 知识图谱：实体（）、概念（）
  • 数据与特征
    • 名词性/类别特征 nominal/categotical
    • 序数特征 ordinal
    • 间隔特征 interval
    • 比例特征 ratio

例如，通过新浪微博一组用户的标签，找出他们的共同特征和个性标签挖掘，可以用 TF-IDF 框架。

数据预处理

  • 数据聚合：将多个特征合并成单个特征
  • 数据集成：将来自多个数据源的数据统一表示——同一属性被明明不同，书写习惯不同（姓名简写、时间表示）
  • 数据离散化：连续数据转化成离散值
  • 特征筛选：找出关键特征（如主成分分析），选取与模型目标（如分类）相关的特征
  • 特征提取：将原来的特征集，以提高数据挖掘的性能，数据聚合可视为一种特征提取。
  • 数据采样
  • 大规模社交网络的用户采样：采样一个较小规模的网络G’来代表整个网络G

频繁模式/关联挖掘

频繁模式是频繁地出现在数据集中的模式（项集、子序列或是子结构）；用 D 表示事务/交易集合，项可理解为一种商品，项集就是包干某种商品的集合。蕴含式 \(A⇒B\) 的支持度和置信度分别为 \[ support(A⇒B)=P(A\cup B)\\ confidence(A⇒B)=P(B|A)={support(A\cup B)\over support(A)} \] 可以理解为，support 表示的是 AB 一起出现的次数，而 confidence 则表示 A 可以推导出 B 的可能性，即 A 相较于其与其他项的关联性来说，和 B 的关联性有多大。

显然，我们要找到频繁模式，就要求 1. 找到的项集必须是频繁的，即有支持度的要求；2. 找到的关联规则必须是强关联的，即有置信度的要求。此外，这样的规则可能有很多，我们希望找到比较大的项集，因此定义

  • 闭项集：X，不存在 X 的超集 \(Y\sub Y\)，使得 D 中 Y 的支持度与 X 相同，即 Y 的支持度要小于 X
  • 最大频繁项集： X，这个是和「频繁」的概念联结起来的，即设定一个最小支持数 min_sup 不少于这个数的项集是「频繁的」，我们要找到最大的那个闭的频繁项集

下面是一个直观的找到频繁项集的算法 Apriori 算法

一图胜千言，先放一个具体的计算例子。前面两个初始化的步骤的频繁的；在每一轮中，从大小为 \(k-1\) 的项集 \(L_{k-1}\) 扩充到 \(k\) 的项集 \(L_k\)。以 \(k=3\) 为例，原本的是第二行最后的那张表 \(L_2\)，通过其和自己连接产生新的候选项集 \(C_3\)，然而考虑到扫描一次的代价可能比较高，我们希望事先剪枝，其利用的一个性质就是，对于一个大小为 \(k\) 的项集，若其是频繁的，则其所有的 \(k-1\) 子项集都是频繁的。于是，如蓝色方框所示，可以对连接的结果进行剪枝，最终得到 \(C_3\) ，然后进行计数，筛选得到 \(L_3\)。

这里还涉及到的一个步骤是如何进行连接，我们事先对所有的项进行排序，然后，考虑到我们要从大小为 \(k-1\) 的项集得到 \(k\) 项集，这就要求连接的两个项集他们差别的项数仅能为 1；另外，事实上可能产生 \(k\) 频繁项集的两个 \(k-1\) 项集，其前 \(k-2\) 项必然是完全相同的，还是之前的想法，\(k\) 项集其所有子项集必然是频繁的，我们这样连接的方式仅仅是一种简单地进行有效筛选的方案。

我们需要综合地来看连接步和剪枝步，他们合起来要做的，就是要从这些 \(k-1\) 项集出发，找到所有的 \(k\) 项集，要求满足其所有子项集均为频繁的（在之前得到的 \(k-1\) 项集中）。

分类

回到了经典的及其学习部分。下面讲了一下一些概念和比较

生成式模型与判别式模型

  • 生成式模型 Generative ，会对 X 和 Y 的联合分布 \(P(X,Y)\) 建模，然后通过贝叶斯公式得到 \(P(Y_i|X)\)，以选取最大概率的那个 \(Y_i\)。常见的有隐马尔科夫 HMM、朴素贝叶斯 NB、高斯混合模型 GMM、LDA 等。
  • 判别式模型 Discriminative，直接对条件概率 \(P(Y_i|X)\) 建模。常见的有线性回归 LR、支持向量机 SVM、神经网络 NN 等。

决策树

朴素贝叶斯

k-最近邻

基于辅助社交的分类

核心思想是：社交网络中的用户行为会受到其邻居的影响，或因其有有邻居相似属性（兴趣、职业等），采取和邻居相同的行为或具有同类别的标签。

社会影响与同质性

该思想与推荐算法中基于用户的协同过滤思想一致。

\[ P(Y_i=1)={\sum_{j\in N(i)}w_{ij}P(Y_j=1)\over |N(i)|} \] 这里的权重是 0-1 的。

回归

  • 线性回归 \[ Y=wx+\epsilon \]

  • 逻辑回归 \[ P(Y=1|x)={1\over e^{-\beta x}+1} \]

模型评估

聚类

  • K-means
  • 层次聚类

对于聚类结果的评估来说，可由以下的准则

  • 内聚性：组内的方差越小越好

  • 离散性：我们希望得到的类之间有更大差异，这里用的一个指标是各个类中心的方差，越大越好

  • sihouette 指数：基本想法还是上面两个，希望组内尽可能靠近，组间尽可能差距大

6-社区挖掘

在这一章节中我们讨论

  • 怎样发现社区？

  • 社区怎样演化？如何研究社区演化？

  • 如何评价发现的社区是否准确/合理？

Social Media Communities

定义

  • 现实社会：具有共同经济、社会或政治兴趣/特点的个体组成的团体
  • 虚拟社会：社交网站/媒体中由志趣相投的用户通过链接或交互关系组成的团体

相较于显式社区（有一个明确的边界，用户知道自己所述什么社区，社区有哪些人），隐式的社区可能包含了某些信息，其挖掘更具有意义和挑战性。

社区发现 Community detection

比较了社区发现和聚类：一个是基于 feature 的，一个则基于网络关系

总结如下

下面是几个基于群组 group 的社区发现算法。思想是：具有某种群组特点的子图是社区。群组的特点包括：平衡性、鲁棒性、模块化、高密度、层次化等。不难发现这些性质和基于成员 member 的社区发现，以及聚类等概念有着密切关联，以下就从这些角度分别讲一下这些算法。

均衡社区 Balanced Communities, Spectral Clustering 谱聚类

社区发现，可以被看成我们对节点进行分类/分割，也即，需要找到对图的分割，使得分割的代价最低。然而，简单定义的 cut 的代价会有一些问题，比如划分的社区不均衡，多把离群点分为单独的一类。

为实现均衡社区的发现，考虑根据所得到的社区的大小做惩罚，具体为下面的 Ratio cut, Normalized cut 的形式，两者实现的思想和效果是类似的。

下面通过矩阵表示的形式来计算一些 cut 的大小 \(c(P_i, \bar P_i)\) ，设 A 为网络表示矩阵，X 为社区关系矩阵，每一行表示某结点所在社区，每一列表示某个社区包含的成员。于是 \[ (X'AX)_{ii}=\sum_{j,k}x_{ji}A_{jk}x_{ki}=x_i'Ax_i\\ =\sum_{jk}y_jy_kA_{jk} \] 其中， \(x_i\) 表示社区关系矩阵的第 i 行。我进一步记 \(y=x_i\) 最终写成了第二行的形式，观察该式，项 \(y_jy_kA_{jk}\)只有当结点 j 和 k 同属于社区 i，并且两者有边相连时才等于 1，因此此第 i 个对角元的含义是：the number of edges that are inside community i。

而根据我们定义的度矩阵 D，可以得到 \[ (X'DX)_{ii}=x_i'Dx_i=\sum_{jk}y_jy_kD_{jk}=\sum_{j}y_j^2D_{jj} \] 也即，对于所有属于社区 i 的元素（\(y_j^2=1\)），求其度数和，所以此第 i 个对角元的含义是：the number of edges that are connected to members of community i。

两者相减，即为此分割的大小。

基于 cut 的大小，我们可以进一步得到比例割、归一化割的形式；因此，我们最终将此社区分割问题转化为一个求矩阵最小迹的问题

  • 但这样的一个问题是 NP-hard 的，我们采用 spectral relaxation；利用谱聚类，我们可以通过计算拉普拉斯矩阵 L 的最小的前 k 个特征向量得到所需的 \(\hat X\) ；
  • 但这样得到的结果中矩阵 X 中的元素并不是整数了；
  • 为了从我们 \(\hat X\) 中恢复 X，我们可以在 \(\hat X\) 上做一遍 K-means 聚类。

emmm 到后面那部分其实有点不太理解，数学是硬伤 Orz（原 slides 中似乎给出了一些说明），下面给了一个例子，帮助直观理解

稳定社区 Robust Communities

这个和之前的团/簇的想法类似，即希望这个社区内部是紧密的：移除其中的边/结点，不会使得这个社区分成两部分。具体有

  • K-vertex connected (k-connected) graph: 至少要移除 k 个节点才能 disconnect 这个图
  • K-edge connected: 至少要移除 k 条边

例如，大小为 n 的完全图为 n-connected graph；一个 cycle 为 2-connected graph

模块化社区 Modular Communities

这里的考量是，假设我们固定了节点的度分布，考虑各个节点之间随机连接，那么这个大小的社区之内会有一个期望的边数；这是随机情况下，而现实中我们假定社区是高度结构化的 far from random，因此我们度量真实的边数与这一期望值的差距。

先考虑节点 \(v_i, v_j\) 之间的边数，对于节点 i 的一条边来说，其连接到 j 的概率为 \({d_j\over \sum_i d_i}={d_j\over 2m}\)，于是总的期望边数为 \({d_id_j\over 2m}\) （分母上做了一些近似处理）。于是，对于一个分区 \(P_x\)，我们可以定义其与「期望值」的距离 \(\sum_{i,j\in P_x}A_{ij}-{d_id_j\over 2m}\) 。整个划分 \(P=(P_1,...,P_k)\) 的距离就是 \(\sum_{x=1}^k\sum_{i,j\in P_x}A_{ij}-{d_id_j\over 2m}\) 。最后归一化处理，得到模块度 Modularity \[ Q={1\over 2m}\sum_{x=1}^k\sum_{i,j\in P_x}A_{ij}-{d_id_j\over 2m} \] 同样，我们利用矩阵对上式进行表达，定义模块度矩阵 \[ B=A-{dd'\over 2m} \] 则 \[ Q={1\over 2m}Tr(X'BX) \] 这里的形式和之前谱聚类的形式是一样的，不同之处在于这里要去最大的那些特征值；此外，在 Modularity 上，这前 k 个特征值必须是正数。

PPT 上还介绍了一些计算方法，Louvain Method

高密度社区 Dense Communities

我们利用一个子图与团 clique 的接近程度来定义其密度： \[ \gamma={|E|\over \binom{|V|}{2}} \] 我们说一个子图 G 是 \(\gamma\)-dense (or quasi-clique) 的，若其满足 \(|E|\ge \gamma \binom{|V|}{2}\)。

这里简要介绍了定义，但没有细展开，相关的算法和寻找 clique 类似：

层次化社区Hierarchical Communities

感觉思想和聚类算法里面的层次聚类相似，也同样包括两种思路

  • Divisive Hierarchical Clustering
  • Agglomerative Hierarchical Clustering

课上介绍了 Newman 算法，是一种自顶向下的思路：从原本的图开始，计算每一条边的「边介数 edge betweenness」，移除其中最大的那些边；迭代下去。

这里的想法是，要找到那些最重要的边，定义边介数的定义为：最短路径经过该条边的节点对数量

社区演变 Community Evolution

社区演变的三种形式

  • 分裂 Network Segmentation
  • 致密化 Graph densification
  • 缩径 Diameter shrinkage

其中第一点比较有意思：大规模网络随时间推移分解成三个部分：巨大结构（超大连通分支）、星状结构、单元素

此外，还有其他的演化路线

社区评价

另外一方面，我们需要对于所找到的社区进行评价，可以分成两类：是否有 Ground Truth。

在有 GT 的情况下，指标包括

  • Precision and Recall, or F-Measure
  • Purity
  • Normalized Mutual Information 归一化互信息

注意到这里的各种指标的计算，以下面的例子来看，我们关注的是两两之间的关系。在一个类中：两个相同类别的节点对属于 TP，不同类别的节点对属于 FP；在两个类之间：不同类别的节点对属于 TN，相同类别的节点对属于 FN。

下面纯度的定义比较简单：即对于 GT 的每一个类来说，找到我们划分出来的社区中包含最多这个类的社区，累计这些数字。

这里涉及到 互信息 MI 的概念，参见 https://en.wikipedia.org/wiki/Mutual_information；简言之，互信息衡量的是两个随机变量之间的关联程度 \[ I(X;Y)=D_{KL}(P_{(X,Y)}||P_X\times P_Y) \] 从 KL 散度的定义式来看，即为联合分布相对于边际分布乘积的差异程度，这个值越高说明 \(X,Y\) 之间的关联性越大。（比相关系数（描述线性关系）更为普遍？）

这里是把 GT 和预测结果都看成是一个分布，计算其互信息，因此注意到 log 内的分子上会有一个 n；为了统一指标，采用 NMI，即除以 \(\sqrt{H(X)H(Y)}\)。

下面介绍了一些在没有 GT 下的指标

比较粗略地提了一些，一方面，可以借助社区成员的属性发现其相似度（发帖内容、个人描述、标签语义等）；另一方面，基于聚类质量的评价指标。

7-社交网络的信息传播

信息扩散 Information diffusion: process by which a piece of information (knowledge) is spread and reaches individuals through interactions.

一个传播过程需要包括：Sender, Receiver, Medium 三个部分

计算传播学简介 Coumputational Communication

  • 是计算社会学的重要分支，与计算新闻学、网络科学等密切相关，是典型的的较差学科研究
  • 研究对象：关注人类传播行为的可计算基础
  • 研究工具：以网络分析、文本挖掘、数据采集、数学建模等为主要分析工具来大规模地手机并分析人类传播行为数据
  • 研究目标：挖掘人类传播行为背后的模式和法则，分析模式背后的生成机制与基本原理
  • 应用场景：可悲广泛的应用于数据新闻、舆情监测、计算广告等场景

信息传播的测量维度

结点传播力测量

  • 社交用户影响力的量化方法
    • 激发回复：回复数量
    • 激发对话：帖子所激发的他人的相互讨论
    • 语义扩散：用户帖子中使用的词语被他人沿用
  • 度中心性
  • 特征向量中心性
  • PageRank 中心性
  • 中间/中介中心性
  • 权威性、中枢性
  • 群体的相关度量

信息传播对于社交网络结构演化的作用

社会网络的信息传播模型 Information Diffusion

这里借用了 SMM 的 Silde 上的图

这里主要是从网络是否可见（explicit/observable）、信息的可获得性两个角度进行划分的，例如羊群效应是在网络可观测、可以得到 public information 的假设下的。

羊群效应 Herd Behavior

描述的是，个体观察所有其他人的行为后，采取与其一致的行为效应，即「随大流/跟风」。

传播实验需要的条件有

  • 个体的选择决定需要遵从一定的顺序
  • 个体是在掌握一定的信息后才做出决定
  • 个体之间无法传递信息：一个人无法知道他人掌握的信息，但是可以通过观察他人的行为来推断他人掌握的信息

典型的例子包括：食客对餐馆的选择（实现看到 A 的评价更好，但实际到了的时候发现 A 没有人而 B 参观人很多）；Milgram’s Experiment（街上静止抬头）；Solomon Asch’s Experiment（1956 推断棒子的长度是 ABC 中哪一个）

介绍了一下羊群效应的贝叶斯建模，即一个 Urn 中放了一红二蓝或是一蓝二红三个球，依次抽取，结合之前的人的推测得到自己当前的推测；在这种情况下，若是前面两个人推测为蓝，那么从第三个人开始无论其抽到什么一个合理的结果都应该是蓝。

  • Herding: we only have access to public information
  • Herding may be intervened by releasing private information which was not accessible before

羊群效应出现的原因在于，每个人仅能得到他人的 public 信息，而其干预手段也是直观的：需要有人公开他的信息；一个经典的例子，就是皇帝的新衣中的孩子。

老师课上还讲了「沉默的螺旋」，描述的内容和羊群效应类似。

该词最早见于伊丽莎白·诺埃勒-诺依曼于1974年在《传播学刊》上发表的一篇论文《重归大众传播的强力观》，她在1980年《沉默的螺旋：舆论一我们的社会皮肤》一文中进一步发展了该理论，认为：

  • 舆论的形成与大众传媒营造的意见气候有着直接的关系，大众传媒为公众营造了一个意见气候，而人们由于对于社会孤立的恐惧会采取集体趋同的行为，导致一方意见的越来越大声疾呼，另一方意见的越来越沉默的螺旋式过程。
  • 意见领袖能够唤醒“沉默的螺旋”
  • 意见领袖具有强大的网络互动能力和影响力，社交媒体中的大多数网民只是充当“狂欢”者，在与自己利益无关的议题讨论中以“围观者”的身份参与。意见领袖通过转发和评论，在庞大粉丝群中起到了示范作用，带动了“沉默的大多数”选择了集体发声，表达自己的意见与看法。粉丝在意见领袖的唤醒作用之下，不再是一群“乌合之众”，成为具有批判能力和思考能力的活跃群体。

信息级联 Information Cascade

An information cascade: a piece of information/decision cascaded among some users, where

  • individuals are connected by a network and

  • individuals are only observing decisions of their immediate neighbors (friends).

定义：信息或决策在一群个体中扩散的过程，例如在社会网络中，个体经常转发（或采取相同决策）邻近好友的发布内容。

类似于人际传播，存在一个「网络」上。在之前的「羊群效应」的例子中，我们假想了一个全局的「公告板」，而现实中每个人不可能共享一个消息源，而是呈现出一个较大的松散的网络形态。这种情况下更类似信息级联，其传播实验需要条件：

  • 个体存在于一个社会网络中；
  • 个体只能观察到邻近好友的决策行为（可获得的信息比羊群效应少）

PPT 上给的经典例子是 1996/1997 年的 Hotmail，其获得用户增长，原因在于，By inserting the tagline "Get your free e-mail at Hotmail" at the bottom of every e-mail sent out by its users.

下面介绍了几个模型

独立级联模型 Independent Cascade Model (ICM)

想象一个社交网络，每个节点仅有 active/inactive 两种状态，有一个信息源（初始集合），收到信息的邻居以一定的概率成为 active 的，即再次传播该信息，这一概率是随机的。

  • 也正因此，称之为 Senter-centric model，以此区别于线性阈值模型，其为 receiver-centric 的

线性阈值模型 Linear Threshold Model (LTM)

上面的模型对于接收者的建模有点粗糙了，这里对于 receiver 有了更为细致的描述：其为每一个待激活的节点设定一个阈值 \(\theta_i\)，若其接收到的周围 active 节点的信号超过了此阈值就会被激活；这里带来的一个好处就是可以建模不同邻居对它的影响，即适用于有向带权网络，另外为了简洁起见，我们对于每个节点的入度权重都做了归一化（即下面的第一个不等式）。

级联传播的平衡与颠覆

考虑上面的线性阈值模型，我们做一些简化处理：每个入度邻居的影响都是一样的，阈值也就是一样的，例如假定每个加点的激活原则是有超过 2/5 个邻居被激活。在这一假设下，我们容易观察到以下的现象：

  • 一种网络的平衡往往会被一个级联传播颠覆，即该信息完全扩散到了整个网络中；
  • 但有些网络中有维持稳定的平衡

我们关注的是，什么能够让级联停止？阻止完全级联的产生？为此，我们定义聚簇：

容易证明，若激活概率为 q，则该信息不会在一个密度大于 1-q 的聚簇中传播。

级联范围最大化

与之相关的一个问题是，初始是用最少的激活结点，达到最终是激活最多的结点。

其应用价值很广泛，如产品营销，用最低的广告代价/预算达到最大的广告效果。

我们形式化地定义该问题：给定一个参数 k（budget），找到一个初始集合 S，以最大化传播效果 \(f(S)\) 。

注意到这里的函数 f 是定义在一个集合上的，当然我们可以理解为是定义在一个维度为 N 的高维空间上的，其满足如下性质

其中，第三个性质，即「次模函数」，用一个经济学的概念来简单解释，就是「边际效益递减」。

对于该问题，不加证明地说明以下 facts

简言之，就是原问题已被证明为 NP-hard，而替代的方案是采取贪婪算法，每次加一个节点进去使得新的集合可以产生更好的效果。

最后，对信息级联的干预手段总结

  • 限制信息（决策）发布者的出链
  • 限制接收者的入链
  • 降低网络节点（个体用户）的激活概率 \(p_{v,w}\)
  • 网络中形成密度较高的聚簇

创新扩散 Diffusion of Innovations

创新扩散的理论试图回答 why and how innovations spread

下面介绍了几个理论。

Ryan and Gross studied the adoption of hybrid seed corn by farmers in Iowa. 新的杂交玉米有耐病虫、耐干旱等优良特性；但是也会有价格高、不能留种（仅能从 provider 中购买）的问题。

根据观察，区分了五类受众：创新者 innovator、早期采用者 early adopter、早期大众 early majority、晚期大众 late majority、落后者 laggard。

第二个理论是 Katz 的二级传播理论。

第三个是 Rogers 提出的创新扩散的过程说：分为了解、兴趣、评估、试验、采纳五个阶段。

接下来，是对于创新扩散的过程进行数学建模，核心公式是下面的这条

其中 \(i(t)\) 衡量的是 t 时刻的扩散因子， \(A(t)\) 是 t 时刻的采纳人数。根据扩散因子的形式不同，可以细化为三种模型。emmm 下面经过积分可得 \(A(t)\) 的具体形式，不给我的微积分只是都还给高数老师了……

流行病模型 Epidemics

和创新扩散理论一样，流行病模型建模的也是一个隐式网络，或者说我们关心的是整体上的传播趋势和人群感染速率，而不是观察具体的传播路径。

一般来说流行病的研究方法包括

  • 接触网络 Using Contact Network：通过观察宿主如何接触来涉及描述流行病在人群网络中发生的方法

  • 全混合 Fully-mixed Method：只分析传染者感染、恢复的速度而不考虑接触网络的相关信息，这是下面的模型所研究的（我们无法得到接触网络，无法了解感染机制）。

根据不同的假设，可以分为下面的四种模型

考虑总人数为 N。在 SI 模型中，仅有 susceptible 和 infected 两类，对于每一个 I 来说，其接触的人数为 \(\beta N\)，于是会感染 \(\beta S\)，于是在这一轮次的总感染人数为 \(\beta IS\) ，用箭头的方式来写，则乘子为 \(\beta I\)。显然满足等式 \(S(t)+I(t)=N\)，根据微分式 \({dS\over st}=-\beta IS\) 可积分得到最终结果。

在 SIR 模型中加入了 recover，并假设感染恢复后不再易感，建立三变量微分方程。

SIS 模型假设患者恢复后仍然易感；SIRS 则假设一部分康复后易感一部分保持免疫，满足微分式 \({dR\over dt}=\gamma I-\lambda R\)

最后介绍了一些干预手段，不过偏向实证，不再赘述。

8-影响力和同质性 Influence and Homophily

我们观察到，在社交网络中连接的个体通常更加相似。

三种原因：影响力、同质性、混杂/混淆

  • 其中，影响力是 connection 造成了 similarity
  • 同质性是 similarity 造成了 connection
  • 混杂则可以看成是环境因素，对于 similarity 和 connection 都有影响

在这一节中，我们研究：

  • how can we measure assortativity 同配性 ?
  • Measure influence or homophily?
  • model influence or homophily?
  • Distinguish between the two?

度量同配性

符号属性 Nominal Attributes

相同属性的节点之间有更大的概率相连

考虑到符号属性的不均衡性，考虑采用 assortativity significance，即实际上同配的边的比例如期望的随机连接的边的比率

进一步作归一化处理

下面是对于模块度的矩阵表示的推导，课件上写得很完整直接搬过来~

序数属性 Ordinal Attributes

不同于之前的每一个节点是符号属性，这里的节点属性为 Ordinal 的，这时我们用「相关系数」来衡量模块度。

具体来说，对于排列好的所有的边，我们把出节点和入节点组合起来分别写为 \(X_L, X_R\) ，然后计算它们之间的相关系数——相关系数越高，说明属性值越高的节点，越倾向于和其他属性值高的节点连接。

另外，注意到对于无向边来说， \(X_L, X_R\) 都含有 2m 个属性值，只是其排列不同，因此 \(EX_L=EX_R, \sigma(X_L)=\sigma(X_R)\) 。

先来算 Covariance

归一化即得到 Person correlation

影响力 Influence

定义：在没有明显的强制措施和直接命令的情况下影响他人的行为或能力。

度量影响力

进一步，我们需要度量影响力

这里给出了一个度量 Blog 影响力的方式，根据入链、出链、长度、评论数四个指标，反映出四种因素，主要最下面的那条式子，而其中如何结合入链和出链，又定义了一个「影响力传播值」Influence Flow: Influence flow describes a measure that accounts for inlinks (recognition) and out-links (novelty). 不太理解这里「新颖性」的度量，引用了很多重量级的博客，同样可能有很高的创新度吧？

我们可以构建不同的指标来度量影响力，从而给每一个用户（如 Twitter）进行排名，对于不同的排名，利用 Spearman 系数比较两者的相关性。

影响力建模

可以分为两个部分

  • 显示网络影响力建模：参考第 7 节中线性阈值模型等
  • 隐式网络影响力建模：我们不知道网络结构，不知道谁影响了谁，只能对于某个用户的影响力随着时间的变化建模（和激活时刻有关）。把每个用户的效应综合起来就得到最终的模型，线性影响力模型 LIM，不过公式没咋看明白。

同质性 Homophily

度量同质性

简单看网络的同配性系数随着时间的变化情况

同质性建模

书上说用的是类似独立级联模型 ICM 的 variation，但似乎和 ICM 的区别还挺大的？而且这个建模好没意义……

区分影响力和同质性 Distinguishing Influence and Homophily

我们需要度量一个同配网络中是影响力还是同质性起到了重要作用，用一些统计方法来 test，以下都假设我们可以得到网络的几个 temporal shapshot

Shuffle Test 洗牌测试 (Influence)

注意到，如果是用之前的基于网络结构中心性之类的方式来定义影响力，那么这样的度量肯定是 静态的；而我们试图基于网络的 时序特征 来进行分析，所以这里关注的是信息的传播，或者说网络上的节点 active/inactive 比例随时间变化的情况。

回过头来理解究竟什么是 影响力？它和同质性的区别在于，其使得网络上节点的属性发生了变化，这里的属性我们很难得到社会学意义上的那种人际关系，比较简单的是看这种 active/inactive 关系。而洗牌测试的思想，就是如果是影响力起到了作用，那么已经起影响作用的节点一定要比被影响的节点在时间上提前被激活；因此，网络 snapshot 的 timestamp 是有意义的，我们调换时间片，观察这种是否会对一些指标发生影响。

初步看下来是这样的，但还是有些难以理解：这里对于影响力的度量，还是采用了 active/inactive 的方式，在我看来更类似于信息的传播，这样的话直观来说网络上的变化肯定是在时序上有意义的，那么这样的测试如何进行（例如，打乱 timestemp 后这里的 \(p(a)\) 怎么计算？）

具体来说，对于一个节点受影响概率的建模采用了 Logistics 回归，并利用 ML 进行参数估计。

边反向测试 The Edge-reversal Test (Influence)

Randomization Test (Influence/Homophily)

这个还是比较容易理解的：既然我们有网络的时序变化记录，那么希望能根据这一变化直接进行度量。变化包括两方面

  • 网络结构的变化：对应于同质性
  • 节点属性的变化：对应于影响力

那么我们可以分别固定其中的一个变量（网络结构或节点属性），看在下一时刻同配性度量的变化影响，得出是否存在同质性或影响力。下式中，\(A(G_t, X_t)\) 表示利用时刻 t 的网络 G 和时刻 t 的属性 X 计算出来的同配性系数。

下面给出了具体的对于影响力的测试算法，这里进行了属性的随机化操作，重复了 n 次，从而得到了测试的 significance level

对于同质性的测量是类似的，不过这里随机化的是图的结构。