Randomizing Social Networks: a Spectrum Preserving Approach
Randomizing Social Networks: a Spectrum Preserving Approach
复制标题
DOI：
10.1137/1.9781611972788.67
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Xiaowei Ying;Xintao Wu
中科院分区：
文献类型：
--
作者：
Xiaowei Ying;Xintao Wu
由于网络数据的激增，理解真实的社交网络的一般属性已经获得了很多关注。网络中的节点是个体，它们之间的链接表示它们之间的关系。由于关系的敏感性、耻辱性或保密性，许多网络应用（如匿名Web浏览）都要求关系匿名。解决这个问题的一个一般方法是将真实网络中的边随机化，并且只公开随机化的网络。在本文中，我们研究了网络的各种属性可能会受到影响，由于随机化。具体来说，我们专注于频谱，因为网络的特征值与许多重要的拓扑特征密切相关。我们还进行了理论分析，在何种程度上可以实现边缘匿名。提出了一种保谱图随机化方法，该方法在保证边匿名性的同时，能更好地保持网络特性，并进行了实验评估。
Understanding the general properties of real social networks has gained much attention due to the proliferation of networked data. The nodes in the network are the individuals and the links among them denote their relationships. Many applications of networks such as anonymous Web browsing require relationship anonymity due to the sensitive, stigmatizing, or confidential nature of the relationship. One general approach for this problem is to randomize the edges in true networks, and only disclose the randomized networks. In this paper, we investigate how various properties of networks may be affected due to randomization. Specifically, we focus on the spectrum since the eigenvalues of a network are intimately connected to many important topological features. We also conduct theoretical analysis on the extent to which edge anonymity can be achieved. A spectrum preserving graph randomization method, which can better preserve network properties while protecting edge anonymity, is then presented and empirically evaluated.