Considerações a Respeito da Mineração de Grafos

Tema: Ciência de Dados, Data Mining

Considerações Iniciais:

A Mineração de Dados, consiste basicamente em: minerar, classificar, agrupar e detectar regras e associações de dados; objetando identificar padrões em conjuntos de dados instanciados e considerados independentes. Entretanto objetos de interesse tangente a abstrairmos maiores informações e obter conhecimento, em muitos casos têm naturezas totalmente distintas, e tipificações diferentes de relacionamentos, o que torna a tarefa mais dificultosa.

Objetivando representar objetos e seus respectivos relacionamentos computacionalmente, utiliza-se normalmente uma estrutura matemática de nome GRAFO. Um grafo (rede) representa um conjunto de objetos, os seus relacionamentos compostos entre si, em caso de haver. Tangente à análise dos grafos, há certa complexidade e envolve várias áreas do conhecimento, tais como: teoria dos grafos, redes complexas e análise social; nesta conjuntura é que temos a Mineração de Grafos, que consiste em analisar os dados que são representados por grafos.

No que refere-se a utilização dos grafos, há grande usabilidade em mineração de dados em redes sociais (Facebook, Twitter, Instagram), e na web, grafos de citações (neste caos o objeto são os autores de artigos, livros e os seus relacionamentos) apenas para citarmos algumas aplicabilidades comuns. É possível também representar por intermédio de grafos os relacionamentos das redes sociais, das amizades, seguidores, curtidas, no caso do Facebook, Instagram; analisando inclusive dados armazenados nas redes sociais sobre, idade, localidade, formação e interesse dos usuários. Pode-se representar com um grafo os relacionamentos em redes sociais, a frequência com que os usuários comunicam-se (curtidas, seguidores, troca de mensagens). Objetiva-se nesta abordagem, introduzir sumariamente os conceitos envolvendo grafos e mineração, intuindo clarificar um assunto/temática em voga atualmente.

Terminologia dos Grafos:

Em um grafo classificado como unimodal, isto é, um grafo simples; consiste objetivamente e pragmaticamente numa estruturação matemática, composta por: V, um conjunto de vértices (denominados nós); E, significando um conjunto de arestas (ligações); e “o”, sendo uma função de E, em V x V, na qual associa cada aresta a um par de elementos V, a sua representação básica é: o(E) V x V. Para fins de terminologia há de se definir os seguintes aspectos: grafo é sinônimo de rede; aresta, conexão e ligação são igualmente sinônimos, além de vértice, objeto e entidade.

Intuindo denotar um grafo, define-se G(V, E, o), sendo “G = grafo”, utilizando também V(G) e E(G), para definir um conjunto de vértices e conjunto de arestas respectivamente.

Um grafo simples, é um grafo com ligações diretas, sem paralelas ou laços, podendo ser expressado da seguinte forma; G com quatro vértices ligados entre si por três arestas. Para os vértices temos V(G) = {v1, v2, v3,v4},e para as arestas temos E(G) = {e1, e2, e3}, a função para esta estrutura é, o = {(v1, v2),(v2,v3),(v4,v2)}, função esta que define o ordenamento das ligações entre os conjuntos de dados V.

Um grafo completo, consiste em um grafo simples, em que há uma aresta ligando cada par de vértices diferentes. Porém no tangente a Mineração de Grafos dá-se uma atenção especial para os grafos denominados bipartidos. Há, nesta tipificação, um conjunto de vértices que está dividido em dois subconjuntos disjuntos, isto é, unindo-se a outros subconjuntos por um vértice. A representação estrutural matemática de um grafo bipartido é a seguinte: G(V,E), em que V(G) = X união Y, X intersecção Y = { }, e E(G) X x Y, a função é X = {v1,v2,v3,v4} e Y = {v5,v6,v7}.

Métricas:

Em um conjunto de entidades e vértices de um determinado grafo, poderá invariavelmente haver entidades que tenham maior influência do que outras. Denomina-se centralidade de um vértice, a medição da relevância de um vértice em relação aos demais. Utilizam-se as métricas para medir o grau de importância de um usuário de uma rede social, ou mesmo uma publicação em específico, em relação a todas as publicações de um usuário, levando em conta o número de visualizações e curtidas por exemplo.

Temos basicamente três tipos de centralidade, conforme o delineado a seguir:

Centralidade de grau: onde um vértice V, definido com grau V, consiste em; quanto maior o número de vizinhos um vértice possui, maior é a sua importância. Numa rede social por exemplo, quanto maior o número de amigos um usuário tem, conclui-se que portanto é mais relevante em detrimento dos demais que possuem números de amigos menores.

Centralidade de proximidade: mede-se o vértices que é mais alcançável em relação aos demais (o melhor caminho), intuindo atingir de forma mais fácil. Calcula-se a proximidade de um vértice V, com base nos comprimentos dos caminhos mais curtos entre V e todos os demais vértices de um grafo G.

Centralidade de intermediação: objeta medir o melhor vértice V, que poderá servir como ponte, um caminho mais curto entre dois outros vértices, de G (grafo).

Os grafos têm uma aplicabilidade clara e importante na mineração de dados em redes sociais, na definição de conteúdos de anúncios e medição da influência de certos usuários destas redes em detrimento dos demais.

(Fonte: Data Mining – R. Goldschmidt, E. Passos, E. Bezerra)