Skip to content

Note

To run this notebook in JupyterLab, load examples/ex6_1.ipynb

Warning: this is a work-in-progress draft

Discover community structure using igraph and leidenalg

See also: https://arxiv.org/abs/1810.08473

Since there are difficulties getting igraph to install correctly across different environments, kglab does not have it as a dependency. Instead you'll need to install the following packages separately:

!pip install cairocffi
!pip install igraph
!pip install leidenalg
Requirement already satisfied: cairocffi in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (1.3.0)
Requirement already satisfied: cffi>=1.1.0 in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from cairocffi) (1.14.6)
Requirement already satisfied: pycparser in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from cffi>=1.1.0->cairocffi) (2.20)
Requirement already satisfied: igraph in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (0.9.8)
Requirement already satisfied: texttable>=1.6.2 in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from igraph) (1.6.4)
Requirement already satisfied: leidenalg in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (0.8.8)
Requirement already satisfied: python-igraph>=0.9.0 in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from leidenalg) (0.9.8)
Requirement already satisfied: igraph==0.9.8 in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from python-igraph>=0.9.0->leidenalg) (0.9.8)
Requirement already satisfied: texttable>=1.6.2 in /home/lorenzo/drwn/.venv/lib/python3.8/site-packages (from igraph==0.9.8->python-igraph>=0.9.0->leidenalg) (1.6.4)

After successful installs, next we'll import the packages:

import igraph as ig
import leidenalg as la

Create a graph based on the Zachary karate club, a famous example used in network science:

G = ig.Graph.Famous("Zachary")

Find a partition, i.e., detect communities with modularity, then plot using python-igraph and cairocffi:

partition = la.find_partition(G, la.ModularityVertexPartition)
ig.plot(partition)

svg


Integration with kglab

from os.path import dirname
import kglab
import os

namespaces = {
    "nom":  "http://example.org/#",
    "wtm":  "http://purl.org/heals/food/",
    "ind":  "http://purl.org/heals/ingredient/",
    "skos": "http://www.w3.org/2004/02/skos/core#",
    }

kg = kglab.KnowledgeGraph(
    name = "A recipe KG example based on Food.com",
    base_uri = "https://www.food.com/recipe/",
    namespaces = namespaces,
    )

kg.load_rdf(dirname(os.getcwd()) + "/dat/recipes.ttl") ;
sparql = """
    SELECT ?subject ?object
    WHERE {
        ?subject rdf:type wtm:Recipe .
        ?subject wtm:hasIngredient ?object .
    }
    """
import igraph as ig

subgraph = kglab.SubgraphMatrix(kg, sparql)
ig_graph = subgraph.build_ig_graph(ig.Graph())
ig_graph.vs[0].attributes()
{'name': 'http://example.org/#Batter', 'label': 'http://example.org/#Batter'}

Serialize to GraphML format:

with open("tmp.graphml", "w") as f:
    ig_graph.write_graphml(f)

Community detection

component = ig_graph.components().subgraph(0)
partition = la.find_partition(component, la.ModularityVertexPartition)
ig.plot(partition, bbox=(600, 500), vertex_label_size=5, margin=50)

svg

Let's look into the community that involves ind:Butter, nom:Pancake, etc.

ig.plot(partition.subgraph(2), bbox=(600, 500), vertex_label_size=7, margin=50)

svg


Last update: 2022-03-23