寇晓宇，吕天舒，张 岩

北京大学 信息科学技术学院，北京 100871

1 引言

随着信息网络规模的急剧增大，网络数据变得复杂多样，通过分析和研究网络的拓扑结构，可以探索到网络中丰富的知识，进而可以提炼出多种高效的营销模式。如在微博、Facebook为代表的社交网络中，一种方式是通过已知的好友关系以及部分属性已知的用户推测出未知用户的属性，进一步得到用户在不同属性类别下的影响力高低，从而利用网络中具有高影响力的用户进行高效营销；另一种方式是通过预测某用户未来的行为，有针对性地进行个性化营销等。

网络中节点的邻居结构可以描述节点间的复杂交互关系，不同的邻居结构往往有不同的意义表达。如微博中用户的关注关系，若某明星A自身有大量粉丝，并且A关注了B，一般情况下，B也是明星或者有高影响力的用户；若A的大量粉丝没有任何粉丝，一般情况下说明A有大量“僵尸粉”但实际影响力不高。目前对于网络拓扑关系的研究中大多数关注直接邻居组成的结构情况[1-2]或者不同跳数邻居的数目情况[3]，很少关注不同跳数邻居组成的结构的影响。为了解决这一问题，本文以三种最为基本的邻居结构进行分析。图1给出一个实例，红色节点为目标节点，邻居A、B为指向目标节点的直接邻居，构成两个第一种邻居结构；邻居C、D构成一个第二种邻居结构，其中邻居D为目标节点的二度邻居；邻居E、F构成一个第三种邻居结构，其中邻居F既是目标节点的一度邻居，也是二度邻居。……