标题： 探索未知社交网络以发现隐藏节点 显示英文标题

标题： Exploring Unknown Social Networks for Discovering Hidden Nodes

摘要： 在本文中，我们解决了在未知社交网络中发现隐藏节点的挑战，提出了三种类型的隐藏节点发现问题，即Sybil节点发现、边缘节点发现和影响者发现。 我们通过采用基于机器学习的图探索框架来解决这些问题。 利用从图探索中逐渐获得的子图结构，我们构建预测模型以在未知社交图中识别目标隐藏节点。 通过实证研究真实社交图，我们研究了图探索策略在揭示隐藏节点方面的效率。 我们的结果表明，我们的图探索策略在发现隐藏节点方面的效率与已知图结构时相当。 具体而言，发现10%隐藏节点的查询成本最多仅为已知拓扑时的1.2倍，而发现90%隐藏节点的查询成本乘数最多仅为1.4。 此外，我们的结果表明，使用节点嵌入（即节点的低维向量表示）进行隐藏节点发现是一把双刃剑：在某些情况下是有效的，但有时会降低节点发现的效率。 基于这一观察，我们研究了使用一种多臂老虎机算法将使用节点嵌入的预测模型与不使用节点嵌入的模型结合起来的效果，我们的分析表明，基于多臂老虎机的图探索策略在各种设置中都能实现高效的节点发现。 显示英文摘要

摘要： In this paper, we address the challenge of discovering hidden nodes in unknown social networks, formulating three types of hidden-node discovery problems, namely, Sybil-node discovery, peripheral-node discovery, and influencer discovery. We tackle these problems by employing a graph exploration framework grounded in machine learning. Leveraging the structure of the subgraph gradually obtained from graph exploration, we construct prediction models to identify target hidden nodes in unknown social graphs. Through empirical investigations of real social graphs, we investigate the efficiency of graph exploration strategies in uncovering hidden nodes. Our results show that our graph exploration strategies discover hidden nodes with an efficiency comparable to that when the graph structure is known. Specifically, the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4. Furthermore, our results suggest that using node embeddings, which are low-dimensional vector representations of nodes, for hidden-node discovery is a double-edged sword: it is effective in certain scenarios but sometimes degrades the efficiency of node discovery. Guided by this observation, we examine the effectiveness of using a bandit algorithm to combine the prediction models that use node embeddings with those that do not, and our analysis shows that the bandit-based graph exploration strategy achieves efficient node discovery across a wide array of settings.