| |
| Acadêmico(a): Gustavo Henrique Spiess |
| Título: Geração de redes complexas com comunidades sobrepostas e comunidades hierárquicas |
| |
| Introdução: |
Redes complexas, como definido por Metz et al. (2007), são grafos com uma topologia
não trivial. Isso é, são grafos onde parte ou toda a informação de interesse não está contida
nos vértices e arestas individualmente, mas em propriedades do conjunto de vértices e
arestas. Esses grafos e as suas propriedades são aplicáveis as mais diversas áreas, como por
exemplo na propagação de uma epidemia (STEGEHUIS; HOFSTAD; LEEUWAARDEN,
2016).
Segundo Girvan e Newman (2002), um dos sistemas do mundo real que se pode
modelar em uma rede complexa é o conjunto de relações sociais. Uma modelagem simplista
desse sistema é a representação de cada indivíduo como um vértice, e vértices adjacentes
sendo pares de indivíduos que se conhecem. Nesse tipo de sistema pode se encontrar
um subgrafo completo, denominado clique (FORTUNATO, 2010). Esse clique pode ser
interpretado como uma propriedade relevante, indicando a presença de que um objeto
composto por esses vértices.
Girvan e Newman (2002) também apontam que outros sistemas, como cadeias alimentares, cadeias de metabolização, redes de transmissão elétrica e redes de computadores
podem ser representadas como redes complexas. Muitas vezes propriedades que se observam
em redes complexas de um domínio estão presentes também nas redes complexas de outros
domínios, mas com interpretações distintas sobre o objeto modelado. Fortunato (2010)
indica isso nas múltiplas discussão e interpretações do que constitui uma comunidade
em uma rede complexa, dividindo-se principalmente em características estruturais, e por
semelhança de vértice.
Largeron et al. (2015) descrevem o que é chamado na literatura de um modelo de
geração algorítmica de redes complexas no qual os vértices do grafo estão dispostos em uma
nuvem de ponto e a distribuição deles em diferentes comunidades leva em conta sua posição
espacial, e as arestas são construídas em função desse pertencimento a uma comunidade.
Akoglu e Faloutsos (2009) descrevem um modelo mais primitivo, que não realiza a atribuição
explícita de comunidades, mas que gera um grafo com essas comunidades. Ressalta-se,
observando o trabalho de Fortunato (2010) de que há uma vasta literatura a respeito
dos processos de detecção dessas comunidades. Observando-se a literatura da qual os
trabalhos de Largeron et al. (2015), Akoglu e Faloutsos (2009) e Slota et al. (2019), é
indicada a existência dos modelos necessários para a geração de redes complexas com
comunidades. No entanto, propriedades adjacentes a presença de comunidades para os
quais existe literatura a respeito da detecção parecem estar pouco presentes em modelos de geradores de redes complexas.
Dessas propriedades de redes complexas para as quais não foram identificados
modelos de geração destampam-se comunidades hierárquicas e comunidades sobrepostas.
Comunidades hierárquicas, ou hierarquicamente ordenadas, são estruturas recursivas que
podem ser encontradas em redes complexas, onde a característica de distribuição de
arestas faz com que comunidades sejam compostas por sub comunidades. Comunidades
sobrepostas são estruturas comunitárias onde vértices podem estar em mais de uma
comunidade simultaneamente, de forma que a descrição das comunidades se dá em uma
cobertura, não em uma partição (FORTUNATO, 2010).
Tendo esse contexto, este trabalho adaptou os modelos presentes na literatura
de geração de redes complexas para a incorporação dessas propriedades, comunidades
sobrepostas e comunidades hierárquicas.
|
| |
|
