# 15 min Intro to Persistent Homology
### <a href="https://ben300694.github.io/" target="_blank">Benjamin Matthias Ruppik</a>, Max-Planck Institute for Mathematics, Bonn

## Filtrations of topological spaces


### Motivating example: Sublevel filtrations

A lot of topological spaces $X$ come with a natural *filtration*,
an increasing union of subspaces $X_{i}$,
i.e. for $i < j$ in the index set we have $X_{i} \subseteq X_{j}$.

Here is an example of a topological space $X$
(with a Morse function $f \colon X \rightarrow \mathbb{R}$) ...



... and the *sublevel set filtration*
$X_{t} = f^{-1}((-\infty, t])$:





### Persistent homology

The $i$-dimensional homology group of a space measures $i$-dimensional holes (or cavities).

\begin{equation}
H_{i}(X) = i\textrm{-dim cycles modulo boundaries}
\end{equation}

Here are some examples of 1-dimensional homology classes:



persist = "to stick around for a long time"

Example where a first homology class persists from its appearance until the end in <span style="color:red">red</span>.

Example where a first homology class appears but soon thereafter is canceled at a maximum in <span style="color:green">green</span>.

**Slogan: Persistent homology measures non-trivial cycles which can be detected in significant parts of the filtrations.**

## Toy data and Simplex trees

### Defining a simplicial complex with filtration





```python
import pandas
import gudhi
import numpy as np
import networkx
from pylab import *
```


```python
# Toy example working with the simplex tree

toy_st = gudhi.SimplexTree()

# 0-simplices in filtration level 0.0
for i in range(0, 5):
    toy_st.insert([i], 0.0)

# 1-simplices in filtration level 1.0
toy_st.insert([0, 1], 1.0)
toy_st.insert([0, 2], 1.0)
toy_st.insert([1, 3], 1.0)
toy_st.insert([2, 3], 1.0)

# additional 1-simplex in filtration level 2.0
toy_st.insert([1, 2], 2.0)

# last 1-simplex and 2-simplex
toy_st.insert([3, 4], 3.0)
toy_st.insert([0, 1, 2], 3.0)

for simplex in toy_st.get_filtration():
    print(simplex)
```

    ([0], 0.0)
    ([1], 0.0)
    ([2], 0.0)
    ([3], 0.0)
    ([4], 0.0)
    ([0, 1], 1.0)
    ([0, 2], 1.0)
    ([1, 3], 1.0)
    ([2, 3], 1.0)
    ([1, 2], 2.0)
    ([0, 1, 2], 3.0)
    ([3, 4], 3.0)





```python
toy_bar = toy_st.persistence(min_persistence=0.0, persistence_dim_max=True)
print(toy_bar)

gudhi.plot_persistence_barcode(persistence=toy_bar, legend=True)
```


```python
gudhi.plot_persistence_diagram(persistence=toy_bar, legend=True)
```

## Persistent homology applied to "real data": Clique complex of a graph

Repository of various graphs: https://networkrepository.com/index.php



Let us take a graph representing a social network:

Quote: "Data collected about Facebook pages (November 2017).
These datasets represent blue verified Facebook page networks of different categories. Nodes represent the pages and edges are mutual likes among them."



```python
def simplex_graph_from_csv(path_to_csv, delimiter=','):
    """
    Input: Path to csv file with list of edges
    
    Output: 1-skeleton of simplex tree
    """
    # Create networkx graph from edge list
    G_nx = networkx.read_edgelist(path_to_csv, delimiter=',', nodetype=int)
    
    # Create simplex tree
    st = gudhi.SimplexTree()

    # Insert vertices into simplex tree
    for v in G_nx.nodes():
        st.insert([v], 0.0)
    # Insert edges into simplex tree
    for e in G_nx.edges():
        st.insert(e, 1.0)

    return st
```


```python
# Import the real data graph and build 1-complex

path_to_fb_pages_food_csv = './datasets/fb-pages-food/fb-pages-food.edges'

fb_pages_food_st = simplex_graph_from_csv(path_to_fb_pages_food_csv)

#for simplex in fb_pages_food_st.get_filtration():
#    print(simplex)

fb_pages_food_bar = fb_pages_food_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
# print(fb_pages_food_bar)

gudhi.plot_persistence_barcode(fb_pages_food_bar, legend=True, max_intervals=0)
```

Clique complex of a graph:
We add a $k$-simplex for any clique of $(k+1)$-many vertices in the graph.



This is also known as the flag complex of a graph.

The clique complex of a graph $G$ can also be interpreted as a Vietoris–Rips complex for the metric space 
where the points are vertices of $G$ and and the distances are the lengths of the shortest paths in $G$.



```python
def simplex_2_complex_from_csv(path_to_csv, delimiter=','):
    """
    Input: Path to csv file with list of edges
    
    Output: 2-skeleton of simplex tree for clique complex
    """
    # Create networkx graph from edge list
    G_nx = networkx.read_edgelist(path_to_csv, delimiter=',', nodetype=int)
    
    # Create simplex tree
    st = gudhi.SimplexTree()

    # Insert vertices into simplex tree
    for v in G_nx.nodes():
        st.insert([v], 0.0)
    # Insert edges into simplex tree
    for e in G_nx.edges():
        st.insert(e, 1.0)
        
    # Inserting cliques with 3 members
    for clq in networkx.clique.find_cliques(G_nx):
        if len(clq) == 3:
            print('Adding clique ', clq)
            st.insert(clq, 2.0)
        
    return st
```


```python
# Import the real data graph and build 2-complex

path_to_fb_pages_food_csv = './datasets/fb-pages-food/fb-pages-food.edges'

fb_pages_food_st = simplex_2_complex_from_csv(path_to_fb_pages_food_csv)

#for simplex in fb_pages_food_st.get_filtration():
#    print(simplex)
```

    Adding clique  [0, 603, 58]
    Adding clique  [3, 352, 40]
    Adding clique  [3, 65, 608]
    Adding clique  [3, 65, 185]
    Adding clique  [3, 65, 450]
    Adding clique  [3, 65, 299]
    Adding clique  [3, 484, 40]
    Adding clique  [3, 377, 608]
    Adding clique  [3, 377, 185]
    Adding clique  [3, 377, 450]
    Adding clique  [3, 377, 299]
    Adding clique  [8, 73, 369]
    Adding clique  [17, 65, 608]
    Adding clique  [17, 65, 185]
    Adding clique  [17, 65, 450]
    Adding clique  [17, 65, 299]
    Adding clique  [21, 329, 441]
    Adding clique  [21, 516, 334]
    Adding clique  [22, 187, 104]
    Adding clique  [23, 257, 157]
    Adding clique  [23, 434, 58]
    Adding clique  [23, 157, 288]
    Adding clique  [31, 449, 193]
    Adding clique  [31, 193, 41]
    Adding clique  [31, 193, 285]
    Adding clique  [31, 518, 327]
    Adding clique  [31, 518, 424]
    Adding clique  [31, 488, 524]
    Adding clique  [31, 491, 424]
    Adding clique  [31, 491, 142]
    Adding clique  [31, 507, 546]
    Adding clique  [39, 576, 603]
    Adding clique  [39, 340, 43]
    Adding clique  [39, 340, 603]
    Adding clique  [40, 240, 484]
    Adding clique  [46, 578, 417]
    Adding clique  [46, 578, 110]
    Adding clique  [46, 578, 86]
    Adding clique  [50, 67, 578]
    Adding clique  [50, 67, 389]
    Adding clique  [50, 67, 183]
    Adding clique  [50, 182, 289]
    Adding clique  [50, 182, 131]
    Adding clique  [50, 182, 389]
    Adding clique  [52, 113, 494]
    Adding clique  [63, 518, 139]
    Adding clique  [65, 240, 608]
    Adding clique  [65, 240, 185]
    Adding clique  [65, 240, 450]
    Adding clique  [65, 240, 299]
    Adding clique  [65, 333, 185]
    Adding clique  [69, 498, 385]
    Adding clique  [69, 498, 253]
    Adding clique  [72, 269, 70]
    Adding clique  [78, 331, 154]
    Adding clique  [79, 491, 357]
    Adding clique  [79, 518, 85]
    Adding clique  [79, 518, 357]
    Adding clique  [79, 518, 414]
    Adding clique  [79, 507, 546]
    Adding clique  [79, 507, 85]
    Adding clique  [81, 290, 563]
    Adding clique  [82, 451, 261]
    Adding clique  [82, 451, 389]
    Adding clique  [84, 329, 545]
    Adding clique  [84, 329, 374]
    Adding clique  [89, 128, 446]
    Adding clique  [89, 136, 155]
    Adding clique  [89, 136, 558]
    Adding clique  [89, 32, 300]
    Adding clique  [89, 300, 182]
    Adding clique  [89, 558, 254]
    Adding clique  [89, 558, 343]
    Adding clique  [89, 54, 275]
    Adding clique  [89, 245, 217]
    Adding clique  [91, 563, 253]
    Adding clique  [93, 146, 567]
    Adding clique  [93, 103, 94]
    Adding clique  [93, 103, 567]
    Adding clique  [101, 545, 124]
    Adding clique  [101, 374, 124]
    Adding clique  [102, 67, 43]
    Adding clique  [106, 305, 583]
    Adding clique  [109, 181, 320]
    Adding clique  [109, 181, 169]
    Adding clique  [115, 145, 485]
    Adding clique  [118, 518, 424]
    Adding clique  [118, 518, 357]
    Adding clique  [123, 179, 491]
    Adding clique  [124, 613, 545]
    Adding clique  [124, 613, 374]
    Adding clique  [130, 288, 340]
    Adding clique  [134, 232, 563]
    Adding clique  [135, 386, 458]
    Adding clique  [135, 446, 128]
    Adding clique  [141, 461, 574]
    Adding clique  [142, 164, 491]
    Adding clique  [154, 533, 214]
    Adding clique  [157, 289, 288]
    Adding clique  [157, 289, 90]
    Adding clique  [157, 289, 510]
    Adding clique  [157, 131, 288]
    Adding clique  [157, 131, 90]
    Adding clique  [157, 131, 510]
    Adding clique  [157, 603, 90]
    Adding clique  [162, 323, 498]
    Adding clique  [162, 323, 610]
    Adding clique  [164, 518, 327]
    Adding clique  [164, 488, 524]
    Adding clique  [164, 491, 424]
    Adding clique  [164, 507, 546]
    Adding clique  [170, 70, 340]
    Adding clique  [170, 70, 383]
    Adding clique  [174, 264, 318]
    Adding clique  [176, 478, 497]
    Adding clique  [176, 478, 362]
    Adding clique  [177, 389, 350]
    Adding clique  [178, 539, 495]
    Adding clique  [181, 476, 258]
    Adding clique  [185, 377, 240]
    Adding clique  [185, 377, 538]
    Adding clique  [185, 377, 356]
    Adding clique  [195, 90, 227]
    Adding clique  [199, 518, 316]
    Adding clique  [199, 518, 566]
    Adding clique  [202, 340, 288]
    Adding clique  [202, 340, 343]
    Adding clique  [203, 345, 435]
    Adding clique  [204, 540, 215]
    Adding clique  [206, 90, 9]
    Adding clique  [206, 90, 473]
    Adding clique  [208, 128, 446]
    Adding clique  [208, 455, 288]
    Adding clique  [208, 340, 288]
    Adding clique  [208, 340, 446]
    Adding clique  [208, 340, 343]
    Adding clique  [215, 405, 540]
    Adding clique  [222, 365, 522]
    Adding clique  [224, 248, 352]
    Adding clique  [224, 262, 470]
    Adding clique  [224, 470, 352]
    Adding clique  [235, 368, 363]
    Adding clique  [235, 472, 244]
    Adding clique  [240, 377, 608]
    Adding clique  [240, 377, 299]
    Adding clique  [240, 377, 450]
    Adding clique  [240, 377, 563]
    Adding clique  [260, 386, 432]
    Adding clique  [260, 386, 458]
    Adding clique  [262, 368, 470]
    Adding clique  [263, 613, 311]
    Adding clique  [265, 4, 254]
    Adding clique  [265, 7, 35]
    Adding clique  [265, 531, 345]
    Adding clique  [265, 531, 67]
    Adding clique  [265, 531, 436]
    Adding clique  [265, 549, 229]
    Adding clique  [265, 43, 360]
    Adding clique  [265, 43, 83]
    Adding clique  [265, 558, 136]
    Adding clique  [265, 558, 254]
    Adding clique  [265, 54, 275]
    Adding clique  [265, 59, 116]
    Adding clique  [265, 576, 128]
    Adding clique  [265, 578, 67]
    Adding clique  [265, 578, 588]
    Adding clique  [265, 68, 242]
    Adding clique  [265, 594, 41]
    Adding clique  [265, 599, 408]
    Adding clique  [265, 599, 346]
    Adding clique  [265, 599, 172]
    Adding clique  [265, 611, 1]
    Adding clique  [265, 611, 136]
    Adding clique  [265, 611, 426]
    Adding clique  [265, 611, 172]
    Adding clique  [265, 611, 432]
    Adding clique  [265, 611, 436]
    Adding clique  [265, 611, 458]
    Adding clique  [265, 611, 361]
    Adding clique  [265, 616, 352]
    Adding clique  [265, 616, 361]
    Adding clique  [265, 111, 229]
    Adding clique  [265, 120, 375]
    Adding clique  [265, 121, 433]
    Adding clique  [265, 121, 227]
    Adding clique  [265, 121, 41]
    Adding clique  [265, 143, 172]
    Adding clique  [265, 143, 397]
    Adding clique  [265, 143, 151]
    Adding clique  [265, 143, 408]
    Adding clique  [265, 159, 32]
    Adding clique  [265, 159, 360]
    Adding clique  [265, 159, 458]
    Adding clique  [265, 159, 397]
    Adding clique  [265, 183, 32]
    Adding clique  [265, 183, 67]
    Adding clique  [265, 183, 166]
    Adding clique  [265, 198, 432]
    Adding clique  [265, 227, 352]
    Adding clique  [265, 227, 436]
    Adding clique  [265, 229, 436]
    Adding clique  [265, 243, 35]
    Adding clique  [265, 243, 116]
    Adding clique  [265, 246, 182]
    Adding clique  [265, 261, 436]
    Adding clique  [265, 261, 397]
    Adding clique  [265, 302, 58]
    Adding clique  [265, 321, 41]
    Adding clique  [265, 321, 404]
    Adding clique  [265, 322, 245]
    Adding clique  [265, 360, 364]
    Adding clique  [265, 360, 404]
    Adding clique  [265, 360, 479]
    Adding clique  [265, 364, 32]
    Adding clique  [265, 364, 458]
    Adding clique  [265, 364, 397]
    Adding clique  [265, 364, 432]
    Adding clique  [265, 375, 404]
    Adding clique  [265, 386, 432]
    Adding clique  [265, 397, 41]
    Adding clique  [265, 397, 169]
    Adding clique  [265, 439, 136]
    Adding clique  [265, 465, 41]
    Adding clique  [265, 479, 432]
    Adding clique  [265, 479, 458]
    Adding clique  [269, 505, 410]
    Adding clique  [276, 555, 619]
    Adding clique  [282, 62, 392]
    Adding clique  [282, 62, 169]
    Adding clique  [289, 325, 238]
    Adding clique  [289, 56, 128]
    Adding clique  [289, 510, 217]
    Adding clique  [291, 67, 248]
    Adding clique  [291, 67, 107]
    Adding clique  [291, 67, 245]
    Adding clique  [292, 518, 328]
    Adding clique  [292, 518, 612]
    Adding clique  [292, 518, 421]
    Adding clique  [293, 570, 155]
    Adding clique  [297, 448, 518]
    Adding clique  [298, 360, 389]
    Adding clique  [299, 377, 538]
    Adding clique  [299, 377, 356]
    Adding clique  [313, 524, 488]
    Adding clique  [319, 522, 619]
    Adding clique  [323, 242, 434]
    Adding clique  [323, 242, 498]
    Adding clique  [325, 131, 238]
    Adding clique  [327, 480, 518]
    Adding clique  [328, 491, 508]
    Adding clique  [328, 518, 508]
    Adding clique  [329, 609, 545]
    Adding clique  [329, 609, 374]
    Adding clique  [335, 518, 414]
    Adding clique  [339, 444, 7]
    Adding clique  [342, 90, 597]
    Adding clique  [342, 343, 372]
    Adding clique  [342, 343, 340]
    Adding clique  [347, 524, 488]
    Adding clique  [348, 424, 518]
    Adding clique  [357, 518, 430]
    Adding clique  [357, 518, 532]
    Adding clique  [362, 429, 478]
    Adding clique  [368, 352, 470]
    Adding clique  [377, 538, 608]
    Adding clique  [377, 538, 450]
    Adding clique  [385, 498, 352]
    Adding clique  [389, 451, 554]
    Adding clique  [389, 451, 182]
    Adding clique  [389, 451, 111]
    Adding clique  [389, 229, 136]
    Adding clique  [389, 229, 554]
    Adding clique  [389, 229, 111]
    Adding clique  [389, 229, 446]
    Adding clique  [389, 454, 432]
    Adding clique  [389, 531, 67]
    Adding clique  [389, 350, 446]
    Adding clique  [403, 526, 517]
    Adding clique  [403, 526, 70]
    Adding clique  [410, 505, 67]
    Adding clique  [416, 67, 248]
    Adding clique  [416, 67, 107]
    Adding clique  [416, 67, 245]
    Adding clique  [421, 518, 524]
    Adding clique  [424, 480, 518]
    Adding clique  [434, 90, 242]
    Adding clique  [434, 90, 597]
    Adding clique  [445, 229, 576]
    Adding clique  [448, 518, 585]
    Adding clique  [448, 518, 487]
    Adding clique  [451, 345, 182]
    Adding clique  [457, 524, 518]
    Adding clique  [459, 340, 288]
    Adding clique  [459, 340, 343]
    Adding clique  [460, 88, 498]
    Adding clique  [463, 182, 350]
    Adding clique  [473, 90, 217]
    Adding clique  [473, 90, 182]
    Adding clique  [473, 245, 217]
    Adding clique  [473, 245, 340]
    Adding clique  [474, 88, 498]
    Adding clique  [474, 88, 550]
    Adding clique  [478, 497, 535]
    Adding clique  [488, 596, 524]
    Adding clique  [491, 612, 515]
    Adding clique  [498, 526, 352]
    Adding clique  [498, 526, 70]
    Adding clique  [498, 242, 248]
    Adding clique  [515, 612, 518]
    Adding clique  [518, 579, 524]
    Adding clique  [518, 566, 524]
    Adding clique  [522, 555, 619]
    Adding clique  [526, 536, 70]
    Adding clique  [526, 536, 558]
    Adding clique  [536, 288, 70]
    Adding clique  [536, 70, 116]
    Adding clique  [536, 558, 136]
    Adding clique  [536, 558, 116]
    Adding clique  [536, 558, 343]
    Adding clique  [550, 238, 90]
    Adding clique  [557, 90, 227]
    Adding clique  [557, 90, 182]
    Adding clique  [557, 90, 151]
    Adding clique  [577, 67, 43]
    Adding clique  [580, 151, 345]
    Adding clique  [580, 151, 143]
    Adding clique  [581, 32, 300]
    Adding clique  [581, 143, 408]
    Adding clique  [581, 143, 172]
    Adding clique  [581, 143, 397]
    Adding clique  [589, 601, 217]
    Adding clique  [593, 576, 288]
    Adding clique  [593, 558, 116]
    Adding clique  [593, 558, 343]
    Adding clique  [593, 340, 343]
    Adding clique  [603, 576, 361]
    Adding clique  [603, 361, 616]
    Adding clique  [603, 558, 198]
    Adding clique  [617, 217, 56]
    Adding clique  [617, 217, 317]



```python
fb_pages_food_bar = fb_pages_food_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
#print(fb_pages_food_bar)

gudhi.plot_persistence_barcode(fb_pages_food_bar, legend=True, max_intervals=0)

gudhi.plot_persistence_diagram(fb_pages_food_bar, legend=True, max_intervals=0)
```

This is still a little boring, since homology classes only appear
at integral time steps.

## The weight rank clique filtration

Quoting from Nguyen, Aktas, Akbas: Bot Detection on Social Networks Using Persistent Homology:


"Instead of working the clique complex of the whole graph, we can
induce a family of simplicial complexes out of the clique complex of the subgraphs of G and track how
homology changes in this family"

"One of the popular filtration methods defined on undirected weighted networks is called
weight rank clique filtration. This filtration, first defined in [22], uses weights as threshold values
δ. The authors first rank the edge weights from wmin to wmax (it can also be done in other direction,
from wmax to wmin as well) and let the parameter increase from wmin to wmax. At each step δ, they just
consider the thresholded subgraph Gδ ⊆ G that is the subgraph with edges of weight larger than δ.
Then, they create the clique complex of Gδ
to obtain the filtration."


```python
# Import the real data graph and build weighted 1-complex

path_to_fb_pages_food_csv = './datasets/fb-pages-food/fb-pages-food.edges'

# Create networkx graph from edge list
G_nx = networkx.read_edgelist(path_to_fb_pages_food_csv, delimiter=',', nodetype=int)
print("Imported graph with", G_nx.number_of_nodes(), "nodes and", G_nx.number_of_edges(), "edges.")

# Create simplex tree
fb_pages_food_st = gudhi.SimplexTree()

# Insert vertices into simplex tree
for v in G_nx.nodes():
    if G_nx.degree(v) != 0:
        fb_pages_food_st.insert([v], 1/(G_nx.degree(v)))


fb_pages_food_bar = fb_pages_food_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
# print(fb_pages_food_bar)

gudhi.plot_persistence_barcode(fb_pages_food_bar, legend=True, max_intervals=0)
gudhi.plot_persistence_diagram(fb_pages_food_bar, legend=True, max_intervals=0)
```


```python
#Insert edges into simplex tree with filtration value the maximum of its endpoints
for e in G_nx.edges():
    fb_pages_food_st.insert(e, max(fb_pages_food_st.filtration([e[0]]), fb_pages_food_st.filtration([e[1]])))

fb_pages_food_bar = fb_pages_food_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
    
gudhi.plot_persistence_barcode(fb_pages_food_bar, legend=True, max_intervals=0)
gudhi.plot_persistence_diagram(fb_pages_food_bar, legend=True, max_intervals=0)
```


```python
# Expand simplex tree by constructing flag complex up to max_dim,
# the filtration of a simplex is the maximal filtration index of its vertices
fb_pages_food_st.expansion(4)

fb_pages_food_bar = fb_pages_food_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
    
gudhi.plot_persistence_barcode(fb_pages_food_bar, legend=True, max_intervals=0)
gudhi.plot_persistence_diagram(fb_pages_food_bar, legend=True, max_intervals=0)
```


```python
def simplex_graph_with_weight_rank_clique_filtration_from_csv(path_to_csv, delimiter=',', max_dim=4):
    """
    Input: Path to csv file with list of edges
    
    Output: Build the clique complex of the graph
    where the vertices are weighted by the reciprocal of their degree
    """
    # Create networkx graph from edge list
    G_nx = networkx.read_edgelist(path_to_csv, delimiter=',', nodetype=int)
    print("Imported graph with", G_nx.number_of_nodes(), "nodes and", G_nx.number_of_edges(), "edges.")

    # Create simplex tree
    st = gudhi.SimplexTree()

    # Insert vertices into simplex tree
    for v in G_nx.nodes():
        if G_nx.degree(v) != 0:
            st.insert([v], 1/(G_nx.degree(v)))
    
    # Insert edges into simplex tree with
    # filtration value the maximum of its endpoints
    for e in G_nx.edges():
        st.insert(e, max(st.filtration([e[0]]), st.filtration([e[1]])))

    
    # Expand simplex tree by constructing flag complex up to max_dim,
    # the filtration of a simplex is the maximal filtration index of its vertices
    st.expansion(max_dim)
    
    return st
```


```python
def simplex_graph_with_normalized_weight_rank_clique_filtration_from_csv(path_to_csv, 
                                                                         delimiter=',', 
                                                                         max_dim=4):
    """
    Input: Path to csv file with list of edges
    
    Output: Build the clique complex of the graph
    where the vertices are weighted by the reciprocal of their degree
    and we have normalized to take the maximal degree into account
    """
    # Create networkx graph from edge list
    G_nx = networkx.read_edgelist(path_to_csv, delimiter=',', nodetype=int)
    print("Imported graph with", G_nx.number_of_nodes(), "nodes and", G_nx.number_of_edges(), "edges.")

    # Calculating maximal degree
    # (will be needed to normalize the filtration later)
    degrees = [val for (node, val) in G_nx.degree()]
    max_degree = max(degrees)
    print("Maximal degree in the graph is", max_degree)
    
    # Create simplex tree
    st = gudhi.SimplexTree()

    # Insert vertices into simplex tree
    # Filtration by degree of vertex, where the degree
    # is scaled linearly to lie in the interval [0, 1]
    for v in G_nx.nodes():
        if G_nx.degree(v) != 0:
            st.insert([v], 1 - G_nx.degree(v)/max_degree)
    
    # Insert edges into simplex tree with
    # filtration value the maximum of its endpoints
    for e in G_nx.edges():
        st.insert(e, max(st.filtration([e[0]]), st.filtration([e[1]])))

    
    # Expand simplex tree by constructing flag complex up to max_dim,
    # the filtration of a simplex is the maximal filtration index of its vertices
    st.expansion(max_dim)
    
    return st
```


```python
# Building normalized filtered clique complex for the food pages graph

path_to_fb_pages_food_csv = './datasets/fb-pages-food/fb-pages-food.edges'

fb_pages_food_normalized_st = simplex_graph_with_normalized_weight_rank_clique_filtration_from_csv(path_to_fb_pages_food_csv, 
                                                                                                   delimiter=',', 
                                                                                                   max_dim=4)

# for simplex in fb_pages_government_st.get_filtration():
#     print(simplex)

fb_pages_normalized_food_bar = fb_pages_food_normalized_st.persistence(min_persistence=-1.0, 
                                                                       persistence_dim_max=True)

# print(len(fb_pages_government_bar))
# for bar in fb_pages_government_bar:
#     print(bar)

gudhi.plot_persistence_diagram(fb_pages_normalized_food_bar, legend=True, max_intervals=0)
```

## Conclusion

We could now analyze the persistence diagrams further
and for example compare the food pages graph with say a politics graph.


```python
# fb-pages_food.edges is already imported above

path_to_fb_pages_government_csv = './datasets/fb-pages-government/fb-pages-government.edges'

fb_pages_government_st = simplex_graph_with_weight_rank_clique_filtration_from_csv(path_to_fb_pages_government_csv, 
                                                                                   delimiter=',', 
                                                                                   max_dim=2)

# for simplex in fb_pages_government_st.get_filtration():
#     print(simplex)


fb_pages_government_bar = fb_pages_government_st.persistence(min_persistence=-1.0, persistence_dim_max=True)

# print(len(fb_pages_government_bar))
# for bar in fb_pages_government_bar:
#     print(bar)

# gudhi.plot_persistence_diagram(fb_pages_government_bar, legend=True, max_intervals=500)

##########

# Comparing different persistence diagrams using the bottleneck distance
# persistence_interval_dim_1_1 = fb_pages_food_st.persistence_intervals_in_dimension(1)
# persistence_interval_dim_1_2 = fb_pages_government_st.persistence_intervals_in_dimension(1)

# print(gudhi.bottleneck_distance(persistence_interval_dim_1_1,
#                                 persistence_interval_dim_1_2))


##########

path_to_fb_pages_politician_csv = './datasets/fb-pages-politician/fb-pages-politician.edges'
```

    Imported graph with 7057 nodes and 89455 edges.



```python
# Unfortunately, this graph as given is too large,
# so we would need to prune it before processing

path_to_fb_pages_sport_csv = './datasets/fb-pages-sport/fb-pages-sport.edges'

fb_pages_sport_st = simplex_graph_with_weight_rank_clique_filtration_from_csv(path_to_fb_pages_sport_csv, 
                                                                              delimiter=',', 
                                                                              max_dim=2)

# fb_pages_sport_bar = fb_pages_sport_st.persistence(min_persistence=-1.0, persistence_dim_max=True)
    
# gudhi.plot_persistence_diagram(fb_pages_sport_bar, legend=True, max_intervals=0)
```

    Imported graph with 13866 nodes and 86858 edges.


### Properties of the data we could detect with persistent homology

 * Qualitative large scale features in the data
 * Measures both the global and local topology of a dataset
 * We can use the persistence data as input for further machine learning applications
 
### Drawbacks of using persistent homology

 * Have to deal with noise in the data and stability
 * For example, points close to the diagonal in the persistence diagram only appear for a short time: these could come from random fluctuations in the data, but could also represent local properties
 * It can be challanging to interpret the meaning of the persistent homology groups for the application

## References

 * An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists: https://arxiv.org/abs/1710.04019
 * Bot Detection on Social Networks Using Persistent Homology: https://www.semanticscholar.org/paper/Bot-Detection-on-Social-Networks-Using-Persistent-Nguyen-Aktas/e3944fac408415965b3d24d52d3ac7b7a0e9aa17
 * Persistent Homology of Collaboration Networks: https://www.hindawi.com/journals/mpe/2013/815035/
 
 
 
### Python libraries used

#### TDA tools

 * [GUDHI Python module](https://gudhi.inria.fr/)
 * https://github.com/GUDHI/TDA-tutorial

#### Graphs

 * https://networkx.org/



### Datasets
 
 @inproceedings{nr,
      title = {The Network Data Repository with Interactive Graph Analytics and Visualization},
      author={Ryan A. Rossi and Nesreen K. Ahmed},
      booktitle = {AAAI},
      url={https://networkrepository.com},
      year={2015}
 }

### Appendix: Vietoris-Rips complex from Distance matrix

We will consider the following graph with 5 vertices where pairwise distances are encoded in the following matrix:


```python
toy_matrix = [[0,1,1,2,inf],
              [1,0,2,1,inf],
              [1,2,0,1,inf],
              [2,1,1,0,inf],
              [inf,inf,inf,inf,0]]
```



Vietoris-Rips filtration for $r \in \mathbb{R}_{\ge 0}$:
Insert a simplex for any finite set of vertices that has diameter at most $r$.


```python
graph_distance_matrix = toy_matrix

# Build Vietoris-Rips complex

skeleton = gudhi.RipsComplex(
    distance_matrix = graph_distance_matrix,
    max_edge_length = 5.0
)

Rips_simplex_tree = skeleton.create_simplex_tree(max_dimension = 3)

for simplex in Rips_simplex_tree.get_filtration():
    print(simplex)
```

    ([0], 0.0)
    ([1], 0.0)
    ([2], 0.0)
    ([3], 0.0)
    ([4], 0.0)
    ([0, 1], 1.0)
    ([0, 2], 1.0)
    ([1, 3], 1.0)
    ([2, 3], 1.0)
    ([1, 2], 2.0)
    ([0, 1, 2], 2.0)
    ([0, 3], 2.0)
    ([0, 1, 3], 2.0)
    ([0, 2, 3], 2.0)
    ([1, 2, 3], 2.0)
    ([0, 1, 2, 3], 2.0)



```python
# Compute persistence of the simplex tree
BarCodes_Rips = Rips_simplex_tree.persistence(min_persistence=0.0, persistence_dim_max=True)

print(BarCodes_Rips)
```

    [(1, (1.0, 2.0)), (0, (0.0, inf)), (0, (0.0, inf)), (0, (0.0, 1.0)), (0, (0.0, 1.0)), (0, (0.0, 1.0))]



```python
gudhi.plot_persistence_diagram(persistence=BarCodes_Rips, legend=True)
```


```python
gudhi.plot_persistence_barcode(persistence=BarCodes_Rips, legend=True)
```

a4ee8d502e839fa6a62fb3d37ebbef9c8f4099db
ipynb
Jupyter Notebook
persistent_homology_15_min_intro.ipynb
ben300694/jupyter-TDA
9a8d55477ba3530b7e0af21cec35644db6c2cd2d
MIT
persistent_homology_15_min_intro.ipynb
ben300694/jupyter-TDA
9a8d55477ba3530b7e0af21cec35644db6c2cd2d
MIT
persistent_homology_15_min_intro.ipynb
ben300694/jupyter-TDA
9a8d55477ba3530b7e0af21cec35644db6c2cd2d
MIT
Qwen/Qwen-72B
1. YES
2. YES