Motif Based Community Discovery
Rui Miguel Capela Fonseca · Open Repository of the University of Porto (University of Porto) · 2018
Complex networks are all around us and they are present in every system we interact with in the real world.By understanding the network we gain knowledge about the real system.One of the most important and difficult tasks in complex networks is the detection of community structures.A community is a set of nodes that are related to each other by some attribute, function or characteristic.One example of a community is, in a social network of football fans, all the fans of a specific team.The classic definition for community detection is to find a group of nodes with dense connections between each other and few connections to nodes that do not belong to that community.The most popular metric for community detection is modularity, a quality function that favors this definition.Community detection methods rely on the optimization of this metric.This metric is however not bullet proof: it has a known resolution limit and it relies on the classic definition of community which is limiting.In 2008, the novel concept of motif modularity was introduced, as a generalization of the modularity metric.It aims to replace the edge in the standard modularity with a motif -a general subgraph.In the original work, the authors tested their ideas with some specific motifs.In this thesis our goal is precisely to offer contributions towards the discovery of motif based communities.We extended the original model by adding the possibility of adding new restrictions, namely specifying classes of communities for each node.We also implemented a framework that will accept any general motif and tries to find a node partition that maximizes the new metric in both directed or undirected unweighted networks.Finally, we tested the model in real networks, showcasing its potential and paving the way for new discoveries.i ResumoRedes complexas estão em todo o lado, e estão presentes em todos os sistemas com que interagimos no dia a dia.Ao estudar estas redes, estamos a ganhar conhecimento sobre o sistema em si.Uma das mais importantes e desafiantes tarefas no estudo de redes complexas é a detecção de uma estrutura de comunidade.Uma comunidade é um conjunto de nós que estão relacionados entre si por meio de atributos, funções ou características.Um exemplo de comunidade é, numa rede que represente de fãs de futebol, todos os adeptos de um determinado clube.A definição clássica de deteção de comunidades é encontrar grupos de nós com muitas ligações entre si e com poucas ligações para outros nós da redes que não pertencem a essa comunidade.A métrica mais popular para deteção de comunidades é a modularidade, uma função qualitativa que favorece esta definição.Muitos dos métodos de deteção de comunidades baseiam-se na optimização desta métrica.Ela não é contudo inatacável: sofre de um conhecido limite de resolução e depende da definição clássica de comunidade, que é limitante.Em 2008 surgiu um novo conceito de modularidade de motivos, ou motif modularity, uma generalização da modularidade.Nesta métrica pretende-se usar o conceito de motivo -um subgrafo geral -em vez de uma simples ligação.Nesse trabalho, os autores testaram a métrica apenas com alguns motivos específicos.O objetivo desta tese é precisamente contribuir nesta área da descoberta de comunidades de motifos.Estendemos os o modelo original, adicionando suporte a motivos com uma propriedade de comunidade.Implementamos uma metodologia que aceita um qualquer motivo geral e procura uma partição de nós que maximize a nossa nova métrica, em redes não pesada dirigidas ou não dirigidas.Finalmente, testamos o nosso modelo em redes reais, mostrando o seu potencial e abrindo o caminho para novas descobertas.