An efficient reconciliation algorithm for social networks
An efficient reconciliation algorithm for social networks
复制标题
DOI：
10.14778/2732269.2732274
复制
发表时间：
2014-01-01
影响因子：
2.5
通讯作者：
Lattanzi, Silvio
中科院分区：
文献类型：
--
作者：
Korula, Nitish;Lattanzi, Silvio
如今人们通常使用多个在线社交网络（Facebook、Twitter、Google+、LinkedIn等）。每一个在线网络都代表了他们“真实的”自我网络的一个子集。一个有趣且具有挑战性的问题是协调这些在线网络，即识别属于同一个人的所有帐户。除了提供对社会动态的更丰富的理解外，这个问题还有许多实际应用。乍一看，这个问题似乎在算法上具有挑战性。幸运的是，一小部分人明确地将他们的账户链接到多个网络;我们的工作利用这些连接来识别网络的很大一部分。我们的主要贡献是第一次用数学形式化问题，并设计一个简单的，局部的，和高效的并行算法来解决它。我们能够证明强有力的理论保证算法的性能良好-建立网络模型（随机图，偏好连接）。我们还通过实验证实了该算法在合成和真实的社交网络数据集上的有效性。
People today typically use multiple online social networks (Facebook, Twitter, Google+, LinkedIn, etc.). Each online network represents a subset of their "real" ego-networks. An interesting and challenging problem is to reconcile these online networks, that is, to identify all the accounts belonging to the same individual. Besides providing a richer understanding of social dynamics, the problem has a number of practical applications. At first sight, this problem appears algorithmically challenging. Fortunately, a small fraction of individuals explicitly link their accounts across multiple networks; our work leverages these connections to identify a very large fraction of the network.Our main contributions are to mathematically formalize the problem for the first time, and to design a simple, local, and efficient parallel algorithm to solve it. We are able to prove strong theoretical guarantees on the algorithm's performance on well-established network models (Random Graphs, Preferential Attachment). We also experimentally con firm the effectiveness of the algorithm on synthetic and real social network data sets.