社交网络中的身份和搜索 论文阅读

一、模型

1、可搜索性的定义：
本文提出的模型定义了一类可搜索的网络，并提出了一种从一个节点搜索网络中其他节点的方法。该模型适用于搜索点对点网络中的数据文件的位置、万维网上的页面和分布式数据库中的信息等问题。

2、维度距离的计算：
将个体i和j之间的相似性$x_{ij}$定义为它们在结果层次结构中的最低共同祖先级别的高度，如果i和j的祖先是同一个，则$x_{ij}=1$。图A中，$x_{ij}=3$;图B中，对于维度h=1，$x_{ij}=1$, $x_{ik}=4$；对于维度h=2，$x_{ij}=4$, $x_{ik}=4$。
3、相识概率：
个体i和j之间的相识概率随着它们各自所属群体的相似度降低而降低。以 $p(x)=c{e}^{-\alpha x}$来建模，其中x是上文提到的两人之间的距离，α是相似性的度量指标（相似的人相关联的趋势）。当α<<1时，只有距离很近的人的自变量x小，相识概率p(x)大，而x稍微增大一点，p(x)急速下降。所以，大部分联系都是距离非常近的人产生的，也即所有的联系都将尽可能的短，个体将只与那些与自己最相似的人联系(即，他们自己的底层群体的成员)，产生一个完全同质的孤立小集团世界；相反，当$e^{-\alpha }=b$（b为分支比）时，任何个体都有同样的可能性与其他个体相互作用，产生一个均匀随机图，此时个体相似与否的概念消失。c是一个规范化常数。
4、独立性假设：
个体以不止一种方式(例如，根据地理位置和职业)分层地聚集于社会世界中。我们假设这些类别是独立的，在某种意义上，一个类别的接近并不意味着另一个类别的接近。例如，两个人可能住在同一个城镇，但没有相同的职业。
5、每个人的坐标向量（个人属性集）：
例如A的维度有H=3个，坐标为[1,102,3],代表职业坐标为1，地理坐标为102，亲属关系坐标为3，根据这些距离，分配邻居，且按相识概率分配朋友。当仅考虑一个维度时（H = 1）, 由相识概率公式，一定有以下不等式：若$e^{-\alpha }<<1$ ，每个人的朋友平均数量z < 同 一个组中的人数g。
6、社会距离的计算：
社会距离$=min${各个维度的距离}即个体$A=[1,102,3]$与个体$B=[2,34,20]$的社会距离为1，因为：他们在第一个维度上的距离最小，等于1。社会距离违反了三角不等式，因为个体i和j可以在$h_1$维度上接近，个体j和k可以在$h_2$维度上接近，但$i$和$k$可以在两个维度上都很远，如图B所示，$x_{ik}=4$。
7、消息的传播：
每个个体向单个邻居转发消息，只提供有关网络的本地信息。在这里，我们假设每个节点i只知道它自己的坐标向量${\hat{v}}_i$，它的近邻网络的坐标向量 ${\hat{v}}_j$，以及给定目标个体的坐标向量${\hat{v}}_t$，但对它的熟人圈以外的节点的身份或网络联系一无所知。

二、实验

1、本文贡献：
本文提出了一个结合了网络联系和社会身份知识的简单算法，该算法类似于贪心算法：设目标元素和当前元素的近邻的特征是已知的，消息链中的每个成员i将消息转发给它的邻居j，后者是在社会距离方面更接近目标t的一个节点。该算法可以高效地引导消息传播。

2、本文目标： 研究确定起始节点，如何在不知全貌的情况下使得传播路径最短。网络传播中，每条链有25%的概率断链（消息传递失败）。本文假定任意消息到达其目标的概率至少是一个固定值r=0.05，以此推算出必须假定消息传递的平均长度不能长于 10.4。

3、实验结论1：【2-3层可搜索性最好】
下图2为H和α的关系图，该图勾画出了可搜索网络区域。实线为人数N=102400的可搜索网络区域的边界，点线为N = 204800的可搜索网络区域的边界，虚线为N = 409600的可搜索网络区域的边界。结果显示，可搜索的网络占据了参数空间(α， H)的广阔区域，也即可搜索性是现实社会网络的普遍属性。可搜索网络的区域随着层次的增大而缩小，在N的有限值处消失，这取决于模型参数；图3为N = 102400数据集，当相似性度量指标α = 0（正方形点线）和α = 2（圆形点线）时，消息完成的概率q(H)，水平线表示阈值的位置r = 0.05。
两个图都证明，2层或3层的时候可搜索性最好。事实上，在小世界实验中，来自不同文化的个体在转发信息时通常使用2层或3层，这是一个有趣的结果。

4、实验结论2：【信息在不同网络中传递所需跳数约为6.7】

最终在优化过参数后，实验证明：信息在不同网络中传递所需跳数的统计图如图4，与社会实验所得平均跳数为6的结果相差不大。