Código de barras de um gráfico

8

Usando homologia persistente, podemos analisar a forma (topológica) de uma nuvem de pontos usando o seguinte método de três etapas:

  • converter o conjunto de pontos em um complexo simples (e existem algumas maneiras diferentes de fazer isso) parametrizado por um parâmetro "noise"
  • Calcule os grupos de homologia deste complexo (novamente parametrizado pelo parâmetro)
  • observe a evolução dos grupos à medida que o parâmetro evolui.

O "tempo de vida" dos diferentes grupos parece uma coleção de intervalos, chamada de "código de barras" da forma.

Existe uma explicação fácil de como é o código de barras se o complexo simplicial é apenas um esqueleto 1 (isto é, um gráfico)? Em outras palavras, suponha que começamos com um gráfico (em vez de um conjunto de pontos) e, em seguida, executamos os dois passos restantes, como acima.

Suresh Venkat
fonte

Respostas:

9

Betti-0 será um intervalo para cada vértice, com um dos intervalos envolvidos desaparecendo sempre que uma aresta conectar dois componentes. Isso será muito semelhante a um traço de um Union-Find em execução no gráfico.

Betti-1 será um intervalo para cada loop fechado essencial; correspondente a uma base atualizada em execução para o Cycle Space . Como se trata de um gráfico, eles aparecerão sempre que for adicionada uma aresta que não conecte dois componentes disjuntos e nunca mais desapareça.

Mikael Vejdemo-Johansson
fonte
3

O gráfico já é um complexo simplicial composto por 0 e 1 simplicidades (nós e arestas). A representação do código de barras é significativa somente quando o complexo simplicial é construído passo a passo, de modo que o complexo na etapa k seja um subconjunto do complexo na etapa k + 1, isto é, os vértices e as arestas são inseridos nele em alguma ordem.

Supondo que os vértices sejam adicionados no "tempo" / "valor do parâmetro" 0 e todas as arestas sejam adicionadas no "tempo" / "valor do parâmetro" 1: o código de barras betti_0 será simplesmente um conjunto de linhas que representam o número de componentes disjuntos de o gráfico e betti_1 serão simplesmente um conjunto de linhas que representam cada loop "básico" no gráfico (consulte o espaço de ciclo de um gráfico).

Existem várias maneiras de construir essas funções de ordenação em um gráfico, por exemplo, calcule qualquer função sobre os vértices (digamos o grau de qualquer vértice) e diga que vértices com graus mais baixos "nascem" antes dos vértices com maior grau. Agora diga que uma aresta é adicionada sempre que os dois vértices existirem. Agora, você pode construir uma visão de homologia persistente do gráfico fornecido na distribuição de graus. Muitas outras funções podem ser construídas, por exemplo, pagerank, laplacianos etc.

gurjeet
fonte
1

O que foi dito acima está correto, mas adicionarei uma ruga interessante que deve ser mais conhecida.

Se você usar a distância do gráfico como seu parâmetro de persistência e calcular a persistência do complexo Rips, também poderá encontrar uma homologia dimensional mais alta. Por exemplo, os números betti de persistência para N pontos igualmente espaçados em um círculo se parecem com:

Nb1b2b3b4b5b6b7b8b9b10b11b123415161171810 019121010 00 011110 0112130 00 011310 011410 010 00 0115140 021610 010 00 00 011710 010 01181510 00 00 00 01

(onde persistência betti number significa apenas contar o número de barras de qualquer comprimento que aparecem em cada dimensão)

A distinção entre essa situação e a pergunta feita é que eu não estou filtrando o gráfico - em vez disso, persisto no espaço métrico abstrato que é realizado pelas distâncias da aresta do gráfico.

Anthony Bak
fonte
t
1
Uma vez que conectamos todos os vértices a uma distância t um do outro, mas também construímos o resto do complexo de rasgos. Ou seja, o que você descreveu é o complexo único do complexo rasga no nível t - se um triplo de vértices estiver conectado, adicionaremos automaticamente uma face etc. É relativamente simples trabalhar o caso N = 6 com caneta e papel cenário.
Anthony Bak
@SureshVenkat - eu percebi que interpretei mal o seu comentário. Não há vértice canônico. Se você quiser pensar apenas no esqueleto único (o gráfico), estou dizendo que para cada vértice você adiciona arestas a todos os vértices na distância t (distância no gráfico original). Você também adiciona simplicidades dimensionais mais altas se todas as faces já estiverem incluídas.
Anthony Bak
@ DavidRicherby - Eu acho que você interpretou mal a minha resposta.
Anthony Bak
@AnthonyBak Você está certo - desculpe. Eu ainda recomendaria uma reformulação, já que a ordem das respostas muda à medida que elas recebem votos. Isso significa que o que estava acima quando você escreveu a resposta não está necessariamente acima quando alguém vem lê-la.
David Richerby