Massachusetts Institute of Technology

esultados almejados

Ao vislumbrar os dados como "gráficos", pesquisadores do MIT mostra como encontrar soluções locais para problemas de outra forma esmagadoramente complexa.

Um grafo é um conjunto de vértices (círculos) ligados por arestas (linhas), um conjunto independente maximal é um grupo de vértices (círculos brilhantes), desconexos entre si, pelo menos, um dos quais é conectado a qualquer vértice omitido do grupo .
Gráfico: Daniloff Christine

Larry Hardesty, escritório da notícia do MITNuma altura em que a Internet coloca uma quantidade incalculável de informação ao alcance de qualquer um, e automatizado experimentos científicos churn para fora de dados mais rápida do que os pesquisadores conseguem acompanhar, e redes de comunicações podem incluir bilhões de pessoas, mesmo as mais simples tarefas de computação pode se tornar tão enorme que iriam sobrecarregar ainda um poderoso supercomputador. Mas às vezes é o suficiente para saber um pouco sobre a solução para um cálculo monstruosos: os biólogos de mineração de dados genômicos, por exemplo, pode estar interessado em apenas um punhado de genes.

No Inovações em conferência Computer Science da Universidade de Tsinghua no início deste ano, pesquisadores do MIT, em conjunto com os colegas na universidade de Tel Aviv, apresentou um novo quadro matemática para encontrar tais soluções localizadas de cálculos complexos. Eles aplicaram a abordagem a alguns problemas clássicos em ciência da computação, que envolvem abstrações matemáticas conhecidas como gráficos.

O exemplo mais conhecido de um gráfico é provavelmente um diagrama de uma rede de comunicações, onde os nós da rede - os equipamentos de comunicação - são mostrados como círculos, e as conexões entre eles são representados como linhas. Um grafo é qualquer combinação de tais círculos e linhas, ou, como dizem os matemáticos, de vértices e arestas. Um fluxograma é outro exemplo de um gráfico, ou um gráfico poderia representar citações de artigos científicos, onde cada vértice é um papel, conectados por arestas com os documentos que citam.

Os gráficos podem representar uma diversidade infinita de dados, mas para qualquer grafo dado, é frequentemente útil para calcular o que é chamado um conjunto maximal independente. Um conjunto independente é aquele em que vértices suficientes foram excluídos do gráfico que não há mais arestas: os vértices restantes são ilhas desertas, nenhum deles ligado a qualquer outro. Um conjunto independente maximal se tentar restaurar qualquer um dos vértices excluída também irá restaurar uma borda. Ou seja, cada vértice esquerdo para fora do conjunto é conectado a um dos vértices do conjunto.

Os representantes da comunidade

Cada vértice de um conjunto maximal independente, portanto, está dentro para um conjunto de vértices conectados. Se o gráfico representa uma malha de citações, por exemplo, um cluster pode ser um conjunto de trabalhos sobre temas relacionados.

Um gráfico pode ter diversos máxima conjuntos independentes, e para um gráfico grande o suficiente, computação mesmo um deles poderia ser uma tarefa excessivamente demorado. Ning Xie, um estudante de pós-graduação do Departamento de Engenharia Elétrica e Ciência da Computação, seu assessor, professor de ciência da computação Ronitt Rubinfeld e Shai Vardi e Gil Tamir da Universidade de Tel Aviv desenvolveu um método eficiente para determinar, para uma determinada região de um gráfico, vértices que são e não são incluídos em pelo menos um dos gráfico máxima conjuntos independentes. A chave para o sistema dos pesquisadores é que, sem ter que especificar o conjunto inteiro, eles podem garantir que a aplicação de seu algoritmo para uma segunda região do gráfico - ou uma dúzia ou uma centena de outras regiões - irá produzir resultados consistentes com o primeiro.

pesquisadores O papel é teórico: não aplicar o algoritmo em qualquer cenários do mundo real. Mas os problemas nas áreas de investigação tão diversas como a bioinformática, química, inteligência artificial, programação e redes têm sido caracterizadas como problemas de cálculo conjuntos independentes.

Seshadhri Comandur, pesquisador de ciência da computação no Sandia National Labs, em Livermore, Califórnia, salienta que - como os investigadores reconhecem em seu trabalho - os outros já propostos algoritmos para o cálculo de soluções locais de problemas complexos. "Houve muitos dos conceitos relacionados que têm sido uma espécie de flutuar", diz ele, mas o MIT e pesquisadores de Tel Aviv ", formalizaram-lo de uma forma interessante e, creio eu, da maneira correta." Ele acrescenta que ele está intrigado para ver se outros algoritmos de computação local também pode ser incluído no âmbito do quadro de pesquisadores novo. "Há um monte de outros resultados que têm um sabor semelhante", diz ele.