Privacidade Diferencial de Arestas para Conectividade Algébrica de Grafos

Os grafos são o formalismo dominante para modelar sistemas multiagente. A conectividade algébrica de um grafo é particularmente importante porque fornece as taxas de convergência dos algoritmos de consenso que sustentam muitas técnicas de controle e otimização multiagente. No entanto, compartilhar o valor da conectividade algébrica pode inadvertidamente revelar informações sensíveis sobre a topologia de um grafo, como conexões em redes sociais. Portanto, neste trabalho apresentamos um método para liberar a conectividade algébrica de um grafo sob uma forma teórica de privacidade diferencial, chamada privacidade diferencial de arestas. A privacidade diferencial de arestas ofusca diferenças entre os conjuntos de arestas dos grafos e, assim, oculta a ausência ou presença de conexões sensíveis. Fornecemos privacidade com ruído de Laplace limitado, que melhora a precisão em relação ao ruído convencional ilimitado. Os valores privados de conectividade algébrica são analiticamente mostrados para fornecer estimativas precisas das taxas de convergência do consenso, bem como limites precisos sobre o diâmetro de um grafo e a distância média entre seus nós. Resultados de simulação confirmam a utilidade da conectividade algébrica privada nesses contextos.