Anonymous social networks present a number of new and challenging problems for existing Social Network Analysis techniques. Traditionally, existing methods for analysing graph structure, such as community detection, required global knowledge of the graph structure. That implies that a centralised entity must be given access to the edge list of each node in the graph. This is impossible for anonymous social networks and other settings where privacy is valued by its participants.In addition, using their graph structure inputs for learning tasks defeats the purpose of anonymity. In this work, we hypothesise that one can re-purpose the use of the HyperANF a.k.a HyperBall algorithm -- intended for approximate diameter estimation -- to the task of privacy-preserving community detection for friend recommending systems that learn from an anonymous representation of the social network graph structure with limited privacy impact. This is possible because the core data structure maintained by HyperBall is a HyperLogLog with a counter of the number of reachable neighbours from a given node. Exchanging this data structure in future decentralised learning deployments gives away no information about the neighbours of the node and therefore does preserve the privacy of the graph structure.
翻译:匿名社交网络为现有的社会网络分析技术带来了一些新的和具有挑战性的问题。传统上,分析图表结构的现有方法,如社区探测,需要全球对图形结构的了解。这意味着中央实体必须能够访问图形中每个节点的边缘清单。对于匿名社交网络和参与者重视隐私的其他环境来说,这是不可能做到的。此外,利用图形结构投入学习任务,无法实现匿名的目的。在这项工作中,我们假设,可以重新使用超亚亚努弗 a.k.a Heperball算法 -- -- 用于近似直径估计 -- -- 来进行隐私保护社区检测,以向朋友建议从匿名的社交网络图形结构中学习、对隐私影响有限的系统。这是可能的,因为HyperBall所维护的核心数据结构是超光谱LogLog,与某个节点可接触的邻居的数目相对应。在将来的分散学习部署中改变这一数据结构,不会透露节点邻居的任何信息,因此确实维护了图表结构的隐私。