Klik maksimal

Pengantar Analisis Jaringan di Python

Eric Ma

Data Carpentry instructor and author of nxviz package

Klik maksimal

Definisi: klik yang, saat ditambah satu simpul, tidak lagi menjadi klik

Sebuah graf dengan lima simpul. Empat simpul membentuk klik: tiap simpul terhubung ke semua simpul lain. Tiga simpul dalam klik disorot hijau. Simpul kelima hanya terhubung ke satu simpul.

Klik maksimal

Definisi: klik yang, saat ditambah satu simpul, tidak lagi menjadi klik

Graf yang sama dengan lima simpul. Kali ini, keempat simpul dalam klik semuanya disorot hijau.

Klik maksimal

Aplikasi: pencarian komunitas

Graf yang sama dengan lima simpul.

Komunitas

Temukan klik
Temukan gabungan klik

Graf yang sama dengan lima simpul.

API NetworkX

find_cliques menemukan semua klik maksimal

Klik maksimal

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)

nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

Klik maksimal

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)
nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

Dua graf, masing-masing dengan lima simpul membentuk klik maksimal.

Klik maksimal

import networkx as nx
G = nx.barbell_graph(m1=5, m2=1)
nx.find_cliques(G)

<generator object find_cliques at 0x1043f1f68>

list(nx.find_cliques(G))

[[4, 0, 1, 2, 3], [4, 5], [6, 8, 9, 10, 7], [6, 5]]

Empat graf: dua klik lima simpul seperti sebelumnya, plus dua graf baru masing-masing dua simpul terhubung oleh satu sisi.

Ayo berlatih!

Pengantar Analisis Jaringan di Python