Labeling Nodes Using Three Degrees of Propagation

The properties (or labels) of nodes in networks can often be predicted based on their proximity and their connections to other labeled nodes. So-called “label propagation algorithms” predict the labels of unlabeled nodes by propagating information about local label density iteratively through the network. These algorithms are fast, simple and scale to large networks but nonetheless regularly perform better than slower and much more complex algorithms on benchmark problems. We show here, however, that these algorithms have an intrinsic limitation that prevents them from adapting to some common patterns of network node labeling; we introduce a new algorithm, 3Prop, that retains all their advantages but is much more adaptive. As we show, 3Prop performs very well on node labeling problems ill-suited to label propagation, including predicting gene function in protein and genetic interaction networks and gender in friendship networks, and also performs slightly better on problems already well-suited to label propagation such as labeling blogs and patents based on their citation networks. 3Prop gains its adaptability by assigning separate weights to label information from different steps of the propagation. Surprisingly, we found that for many networks, the third iteration of label propagation receives a negative weight.
AvailabilityThe code is available from the authors by request.

网络中节点的属性（或标签）通常可基于其邻近性以及与其他已标记节点的连接关系进行预测。所谓的“标签传播算法（label propagation algorithm）”，通过在网络中迭代传递局部标签密度信息，完成未标记节点的标签预测任务。这类算法兼具快速、简洁且可扩展至大型网络的优势，却仍能在基准测试问题上时常优于运行缓慢且复杂度极高的算法。然而，本文证明此类算法存在固有局限性，使其无法适配部分常见的网络节点标注模式。为此我们提出一种全新算法——3Prop，它保留了传统标签传播算法的全部优势，却具备更强的适应性。实验结果表明，3Prop在那些不适合传统标签传播的节点标注任务中表现优异，包括蛋白质与遗传互作网络中的基因功能预测、社交好友网络中的用户性别预测；同时在已适配标签传播的任务中也略有提升，例如基于引用网络的博客与专利分类任务。3Prop通过为不同传播步长的标签信息分配独立权重，实现了更强的适应性。令人意外的是，我们发现在诸多网络中，标签传播的第三次迭代会获得负权重。可用性：研究者可通过向作者申请获取该算法代码。