Populational Announement Logic (PPAL)

É uma variante de Public Announcement Logic (PAL), onde o conhecimento é representado sobre populações e grupos, ao invés de sobre agentes discretos como é comumente feito na literatura.

A PPAL foi apresentada na minha dissertação de mestrado em 14/07/2016.

Populações e grupos

Nesta lógica, introduzimos conceitos de populações e grupos ao invés de agentes. Anúncios agem sobre frações de populações/grupos, criando novos grupos a partir deles.

Definição: Uma população representa um conjunto de indivíduos. Uma população $P$ possui tamanho $\overline{P} \in \mathbb R_{>0}$.

Definição: Um grupo pode ser vazio, uma população ou um conjunto disjunto de grupos: \[ G := \emptyset \ | \ P \ | \ \{ G_0, G_1, \dots, G_n \} \]

Modelo (População)

Como veremos adiante, anúncios agem sobre frações de populações/grupos, dessa forma criando diferentes "mundos" para quem recebeu ou não o anúncio. Por esse motivo, o conceito de "muitos mundos" é aplicado.

Definição: Um modelo para uma população $P$ é composto de:

• Um conjunto de estados $T$;
• uma função de valoração $V : \Phi \to 2^T$ que indica proposições verdadeiras para cada estado;
• Uma família de relações binárias $\stackrel{M_P, G}{\sim}$ para cada grupo $G$ conhecido por esta população.

Modelo (Grupo)

Definição: Um modelo para um grupo $G= \{ G_0, G_1, \dots, G_n \}$ é definido a partir do conjunto de modelos de cada um dos seus grupos da seguinte forma: \[ M_G = M_G = \langle T, \stackrel{M_{G_1}}{\sim} \cup \stackrel{M_{G_2}}{\sim} \cup \dots \cup \stackrel{M_{G_n}}{\sim}, V \rangle \]

Linguagem

\[ \varphi ::= p \ | \ \neg \varphi \ | \ \varphi_1 \wedge \varphi_2 \ | \ \varphi_1 \vee \varphi_2 \ | \ \varphi_1 \rightarrow \varphi_2 \ | \\ K_G \varphi \ | \ B_G \varphi \ | \ [\varphi_1]_G^r \varphi_2 \] onde $r \in U = [0, 1]$, $G$ denota um grupo e $p \in \Phi$.

Anúncio

Resumindo (exemplo)

Evaluando $[l]^{0.3}_G B_G(l \land b)$:

\[ B(\varphi, (M_G, r), G) = \\ = \sum_{G' \in G} \frac{\overline{G'}}{\overline{G}} B(\varphi, (M_G, r), G') = \\ = 0.3 \cdot 1/2 + 0.7 \cdot 1/4 = 0.325 \]

Note que:

\[ K(\varphi, (M_G, r), G) = 0 \]

DaLí 2017

Nos dias 23 e 24 de Setembro de 2017 o workshop "Dynamic Logic: new trends and applications" (DaLí) ocorreu na Universidade de Brasília (UnB).

Na conferência, foi apresentado, dentre outros, o trabalho de S. Smets e F. R. Velázquez-Quesada: "The Creation and Change of Social Networks: a logical study based on group size".

Redes sociais

O artigo citado anteriormente apresenta abordagens de lógica modal para a modelagem e estudo de redes sociais.

As redes socias são criadas considerando-se as distâncias entre os agentes, que são definidas como as diferenças entre suas propriedades (ou preferências).

Número de Dunbar

O número de Dunbar $\lambda$ [Dunbar, 1992] é definido como o tamanho máximo da rede social que um agente pode possuir.

A motivação é a própria limitação cognitiva de uma pessoa em conseguir manter relacionamentos sustentáveis com tamanho número de indivíduos.

Modelando redes sociais na PPAL

Inspirando-se nas ideias anteriores, a métrica de distância usada na definição das redes socais para PPAL são os interesses dos grupos.

Definimos os interesses a partir da matriz de interesses: \[ I_{M, w}(G) = \{p \mid \mathcal{I}_{M, w}[G, p] = True\} \] Exemplo:

Camadas sociais (distâncias)

Camadas sociais (interesses)

Camadas sociais (definição)

A distância social de um grupo $A$ para um grupo $B$ é: \[ SD_{M, w}(A, B) = \lvert I(A) \cup I(B) \rvert - \lvert I(A) \cap I(B) \rvert \]

Evaluação do operador de camada social $\odot_{G'}^{A,n} \varphi$: \[ E_{M_G, s}(\odot_{G'}^{A,n} \varphi) = E_{M_{G'}, s}(\varphi) \] onde $G' = \{g \in \mathcal{G}_A \mid SD_{M, w}{(A, g)} \leq n\}$ e $\mathcal{G}_A$ é o conjunto de todos os grupos.

Camada superior

É a camada mais externa dentre as camadas sociais de um grupo.

\[ M, w \uparrow A = max_{X \in \mathcal{G}_A} \{SD_{M, w}(A, X)\} \]

Para qualquer distância $m \geq M, w \uparrow A$, consideramos que: \[ \odot_{G'}^{A, m}(\varphi) = \odot_{G'}^{A, (M, w \uparrow A)}(\varphi) \]

Podemos usar a notação $\odot_{G'}^A(\varphi)$ como abreviação de $\odot_{G'}^{A, (M, w \uparrow A)}(\varphi)$.

Caso-de-uso: "fake news"

Nesse caso de uso, o objetivo é analisar como notícias falsas, ou "fake news", se espalham por uma rede social. O tema ganhou fama após a campanha presidencial de 2016 nos Estados Unidos.

O desafio desse caso de uso é modelar o conflito entre notícias reais e falsas, e o que leva uma população a acreditar em algo.

Caso-de-uso: "peer pressure"

Nesse caso de uso, o objetivo é analisar como as preferências das conexões de um agente em uma rede social influenciam nas próprias preferências do agente. Isso é denominado "pressão de colegas", ou "peer pressure".

O desafio desse caso de uso é como modelar a passagem de tempo e evolução do estado da rede.

Comparação com redes sociais "tradicionais"

Um caminho que deve ser explorado é a comparação da abordagem aqui apresentada e a abordagem tradicional para redes sociais.

Redes sociais normalmente são divididas em três níveis distintos de abstração: micro, meso e macro.

Níveis de abstração

No nível micro, o foco é em indivíduos, e suas interações diretas com outros. Não é nosso objetivo de estudo, já que na PPAL indivíduos nunca são endereçados diretamente.

No nível meso, populações e grupos e suas relações são estudadas.

No nível macro, populações e grupos também são estudados, porém estamos mais interessados em desfechos globais e fatos sobre toda a rede.

Centralidade

Centralidade é uma métrica importante da relevância de um nó para uma rede. Em análise de grafos convencional, a centralidade de proximidade é a distância média dos caminhos mais curtos entre o nó e todos os outros nós do grafo.

Normalmente a métrica de distancia usada é a geodésica (número de arestas mínimo conectando os vértices). Aqui usaremos a métrica de distância social definida anteriormente.

Centralidade de proximidade normalizada

A centralidade de proximidade normalizada de um grupo $G$, é definida através da soma de distâncias de $G$ até todos os outros grupos, variando de $0$ a $1$: \[ C_{M, w}(G) = \frac{\overline{\mathcal{G}_G} - 1}{\overline{\mathcal{G}_G} - 1 + \sum_{X \in \mathcal{G}_G} SD_{M, w}(G, X)} \]

Centralidade (visualmente)

Nesta imagem vemos as distâncias sociais entre grupos (e não os relacionamentos entre estados do modelo). \[ C_{M, w}(A) = \frac{5}{5+1+1+2+1+3} = \frac{5}{13} \approx 0.385 \]

Especificação de modelos

Um dos problemas comuns em verificação de modelos é a dificuldade para especificação dos modelos.

Os verificadores mais comumente utilizados atualmente recebem modelos iniciais a partir da especificação explícita dos estados.

Estruturas de Kripke

Estruturas de Kripke são a forma mais comum de representação de modelos semânticos para lógicas modais e relacionadas.

Proposta: um formato de especificação padrão para qualquer modelo de Kripke.

Um padrão para especificação

• Uma sintaxe para especificação de modelos;
• Modelos iniciais a partir de parâmetros:
  • Número de proposições distintas;
  • Número de agentes/modalidades;
  • Estado inicial.
• Padrões de programação funcional para transformação e redução do modelo.

Programação funcional

Programação como evaluação de funções, evitando efeitos colaterais e dados mutáveis.

• map: aplica uma função a cada elemento de uma estrutura, resultando numa nova coleção com os resultados;
• filter: aplica uma função aos elementos de uma estrutura, retornando apenas os elementos cuja função resultou em true;
• reduce: aplica uma função de combinação a uma estrutura recursiva, resultando em um único elemento.

Verificação de modelos para redes sociais

Redes sociais são estruturas complexas, e por isso a capacidade de especificação de modelos é tão importante.

Com o auxílio do ferramental de especificação de modelos, espera-se que seja possível analisar e extrair resultados relevantes sobre redes sociais realísticas.