GePhi

Fase I - Estudo

Título da Idéia

Gephi

Objetivos

Desenvolver um plugin para o software Gephi, que suporte os algoritmos SPLC (Search path link count) e SPNP (Search path node pair).

Conceito

• Gephi é um software de código aberto que permite a visualização e extração de informações em redes modeladas através de grafos.
• Com o Gephi, é possível aplicar diversos algoritmos e técnicas na rede, afim de descobrir novas relações e informações que são difíceis de se obter ou enxergar a priori.
• Por se tratar de um software livre, o Gephi permite que crie seus próprios algoritmos e os adicione como um plugin na plataforma.
• Com os algoritmos SPLC ou SPNP , conseguimos identificar tecnologias promissoras em uma rede de citação de patente. Essa rede, é construída obedecendo a seguinte relação: Se uma tecnologia A contribui de alguma forma para o desenvolvimento de uma tecnologia B, representamos essa relação com uma aresta A->B.

• Search Path Link Count de uma aresta, refere-se a quantidade de vezes que passamos por ela, se considerarmos todos os caminhos do grafo que terminam em um nó sink (grau de saída zero). Seis caminhos atravessam a aresta D-F, portanto, fornecem o valor de SPLC 6. Eles são: BDFHK, BDFIL, BDFIMN, DFHK, DFIL, e DFIMN.

• Search Path Node Pair de uma aresta u-v, refere-se a quantidade de vezes que passamos por ela, se considerarmos todos os caminhos começando de um nó ancestral de u (incluindo ele mesmo) e que termine em um nó descendente de v (incluindo ele mesmo). Os valores de SPNP da aresta C-H é 6 pois há 6 caminhos que começam em A, B, C (A e B são ancestrais de C) e terminam em H e K (K é o descendente de H). Esses caminhos são ACH, ACHK, BCH, BCHK, CH e CHK.

• Ambas as medidas tem o propósito de trazer a significância de uma aresta e foram propostas por Hummon e Doreian.

Características 

• Inicialmente foi necessária a leitura de alguns artigos científicos relacionados aos algoritmos afim de entender alguns aspectos como, funcionamento, complexidade, tipos de problemas em que pode ser aplicado e limitações. Foi feito um estudo do software Gephi, afim de entender seu funcionamento, aplicações e também entender a sintaxe em que os dados devem estar para que ele reconheça como uma rede. Os algoritmos foram implementados nas linguagens JAVA e C++ e teve como base o algoritmo de busca em profundidade.
• No momento, foi criado um programa com interface gráfica como solução temporária, onde o usuário pode escolher um arquivo contendo o grafo, e então permite calcular os valores SPLC para cada aresta e também encontrar os caminhos principais do grafo selecionado. Como o grafo precisa ser direcionado e sem ciclos, foi criada uma opção no programa para remover os ciclos do grafo. A saída mostrada na imagem abaixo refere-se ao grafo mostrado na seção Conceito.
  

• A integração com o Gephi esta na fase final. Utilizando a ferramenta Apache Maven (https://maven.apache.org), foi possível compilar o código descrito acima, junto ao Gephi, o que significa que nosso programa já é reconhecido pelo Gephi como um plugin. Para a conclusão do projeto, será necessário adicionar um botão na interface do Gephi para executar o plugin criado e atualizar a interface criada para uma interface com padrão Gephi.

Estudo Dirigido

• Verspagen, Bart. (2007). Mapping Technological Trajectories as Patent citation Networks: a Study on the History of Fuel Cell Research. Advances in Complex Systems (ACS). 10. 93-115. 10.1142/S0219525907000945.

• Norman P. Hummon, Patrick Dereian,

Connectivity in a citation network: The development of DNA theory, Social Networks, Volume 11, Issue 1, 1989, Pages 39-63, ISSN 0378-8733, https://doi.org/10.1016/0378-8733(89)90017-8. (http://www.sciencedirect.com/science/article/pii/0378873389900178)

• https://en.wikipedia.org/wiki/Main_path_analysis

• https://github.com/gephi/gephi

Fase II - Ensino

Conteúdo

O conteúdo da página GePhi será atualizado constantemente de acordo com a evolução dos estudos e implementações, proporcionando um melhor entendimento sobre o projeto.

Apresentação

Apresente ao grupo (reunião, EAD, Blog, ...)
Publique aqui

Fase III - Exemplo de Caso de Negócio

Benefícios para quem for oferecer esta solução

• Código Open Source
• Simples de usar
• Leve e rápido
• Pouquíssimos softwares semelhantes

Benefícios para o usuário

• O Gephi é uma das ferramentas mais completas para a visualização de redes baseadas em grafos
• O algoritmo implementado para o plugin, se propõe a identificar tecnologias promissoras em redes de patentes, o que é algo recente e inovador.
• O Gephi pode auxiliar qualquer pessoa que trabalhe com redes grandes a descobrir novos padrões e informações da rede.
• É possível aplicar diversos algoritmos e técnicas com um simples clique do mouse.
• Possui ferramentas para manusear grafos, tornando mais rápido e simples a criação e modificação de grafos.

Direcionadores chave para esta iniciativa

• Visualização de redes modeladas por grafos
• Extração de informações e padrões relevantes de redes
• Identificação de tecnologias promissoras em redes de citação de patente

Possíveis modelos de negócios

    Descrever em tópicos os possíveis modelos de negócios

Business Case

    Descrever um exemplo de negócio que permita avaliar a solução comercialmente

Fase IV - Protótipo orientado ao Negócio

Escopo

• Um protótipo foi feito como medida temporária até a finalização do projeto, implementado na linguagem Java e utilizando a biblioteca gráfica Swing.

Limitações

• É necessário modelar um arquivo com a rede para os padrões aceitos pelo Gephi.
• Pode não ser muito rápido na execução de algoritmos muito complexos em redes extremamente grandes
• Requer Java 8 ou superior para execução
• Muito difícil desenvolver plugins em linguagens que não sejam especificamente Java

PoC

Desenvolva um PoC (Proof of Concept)

Detalhamento Técnico

Descreva especificamente os aspectos técnicos desta pesquisa

Pesquisadores

• Vinícius Henrique Resende
• Pedro Diogo
• Alex Fabiane