558
个编辑
更改
→Bigbang algorithm
====Bigbang algorithm====
====Bigbang algorithm====
[[文件:MDS方法.png|缩略图]]
[[文件:MDS方法.png|缩略图]]
在论文《A Geometric Representation of Collective Attention Flows》中，研究者采用了简化版 BigBang 算法，将网站之间的流距离嵌入到高维欧几里得空间中，从而构建集体注意力流的几何表征。
== 基本思想 ==
BigBang算法的目标是：给定一组节点之间的目标距离，在 <math>d</math> 维欧几里得空间中为每个节点分配一个坐标，使嵌入空间中的欧氏距离尽可能接近原始距离。
设节点 <math>i</math> 在 <math>d</math> 维空间中的坐标为 <math>V_i^d</math>，节点 <math>j</math> 的坐标为 <math>V_j^d</math>，二者之间的目标距离为 <math>c_{ij}</math>。算法希望满足：
<math>
\|V_i^d - V_j^d\| \approx c_{ij}
</math>
其中，<math>\|V_i^d - V_j^d\|</math> 表示节点 <math>i</math> 与节点 <math>j</math> 在嵌入空间中的欧氏距离。
== 在集体注意力流研究中的应用 ==
在《A Geometric Representation of Collective Attention Flows》中，作者首先基于用户点击流数据构建开放流网络，并计算网站之间的流距离。由于原始流距离通常是非对称的，论文将节点 <math>i</math> 到节点 <math>j</math> 的流距离 <math>l_{ij}</math> 与反向流距离 <math>l_{ji}</math> 相加，得到对称流距离：
<math>
c_{ij} = l_{ij} + l_{ji}
</math>
随后，研究者使用简化版 BigBang 算法，将网站嵌入到 <math>d</math> 维欧几里得空间中，使网站之间的欧氏距离近似对应于其对称流距离 <math>c_{ij}</math>。
== 算法过程 ==
论文中采用的简化版 BigBang 算法主要包括初始化、调整和微调三个阶段。
=== 初始化 ===
在初始化阶段，算法在 <math>d</math> 维欧几里得空间中为每个节点随机分配一个初始位置。设节点 <math>k</math> 的初始坐标为：
<math>
V_k^d
</math>
其中，<math>d</math> 表示嵌入空间的维数。
=== 调整阶段 ===
在调整阶段，算法采用类似弹簧模型的方法调整节点位置。任意两个节点之间被看作由一根弹簧连接，弹簧的自然长度等于二者之间的目标距离 <math>c_{ij}</math>。
若嵌入空间中的欧氏距离大于目标距离，则节点之间产生吸引作用；若欧氏距离小于目标距离，则节点之间产生排斥作用。
两个节点之间的嵌入误差可表示为：
<math>
E_{ij}^{(1)}(V_i,V_j)=\|V_i^d-V_j^d\|-c_{ij}
</math>
当 <math>E_{ij}^{(1)}>0</math> 时，表示嵌入距离大于目标距离，节点需要相互靠近；当 <math>E_{ij}^{(1)}<0</math> 时，表示嵌入距离小于目标距离，节点需要相互远离。
论文中，该阶段持续进行，直到整体误差低于给定阈值。在相关实验中，该阈值设为 <math>1.50</math>。
=== 微调阶段 ===
在微调阶段，算法进一步根据嵌入畸变对节点位置进行修正。对于任意两个节点 <math>i</math> 和 <math>j</math>，其距离比例偏差定义为：
<math>
d_{ij}=
\max \left(
\frac{\|V_i-V_j\|}{c_{ij}},
\frac{c_{ij}}{\|V_i-V_j\|}
\right)
</math>
嵌入畸变定义为：
<math>
E_{ij}^{(2)}=(d_{ij}-1)^2
</math>
整体平均嵌入畸变可表示为：
<math>
\delta =
\frac{1}{N^2}
\sum_{i=1}^{N}
\sum_{j=1}^{N}
d_{ij}
</math>
其中，<math>N</math> 表示节点总数。算法继续调整节点位置，直到平均嵌入畸变 <math>\delta</math> 小于预设阈值。论文中使用的阈值为 <math>1.14</math>。
== 特点 ==
* '''距离保持'''：算法的核心目标是使嵌入空间中的欧氏距离尽可能接近原始网络距离。
* '''弹簧模型'''：节点之间的调整过程类似物理弹簧系统，距离过大时相互吸引，距离过小时相互排斥。
* '''适用于高维嵌入'''：该算法可以将节点嵌入到较高维度的欧几里得空间中，以降低距离失真。
* '''可用于网络可视化'''：高维嵌入结果可进一步通过主成分分析等方法投影到二维空间中进行可视化。
* '''保留整体结构'''：算法考虑所有节点对之间的距离关系，因此能够反映网络的全局几何结构。
====MDS====
====MDS====