Graphlet

As explained in Graph Algorithms for Data Science

A graphlet is a node position within a distinctly connected subgraph consisting of a specified number of nodes.

A graphlet records a node’s position in a distinctly connected subgraph containing a specified number of nodes. Counting graphlets encodes the node’s direct neighborhood, helping compare users with similar network roles even when they are not adjacent. section 8.1.1

In a directed follower network, graphlet counts describe local relationship patterns:

• A two-node graphlet contains two nodes and directed relationships; its positions represent outgoing, incoming, or bidirectional connections. section 8.1.1
• Count the position occupied by a node: outgoing connections count one position, incoming degree counts another, and mutual following represents a friend pattern. section 8.1.1
• An analyst can calculate incoming and outgoing degrees for every user and store friend-pattern counts as node properties. section 8.1.1

Figure 8.4 Two-node graphlets

Use the two-node graphlet diagrams to distinguish directed relationship patterns and their node positions. section 8.1.1

Figure 8.5 Counting two-node graphlets

Use the counting diagram to connect graphlet positions with a node’s incoming, outgoing, and mutual relationships. section 8.1.1

How Graph Algorithms for Data Science covers it

How deep it goes

Defines graphlets and works through two-node directed counts, while only introducing three-node graphlets for further analysis.

Examples

Uses a directed follower network, incoming and outgoing degrees, mutual following, and stored friend-pattern counts.

What you can do after

Practice/perform graphlet counting by measuring user degrees and storing friend-pattern counts as node properties.

How it connects

Connects graphlets to motifs, local neighborhood features, node roles, and network similarity analysis.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Related concepts

• structural motifcontrasts with · A structural motif is a recurring local arrangement of connected components within a graph or molecule.
• local neighborhooduses · A local neighborhood is a set of elements considered near a specified element according to a defined spatial, topological, distance-based, or relational criterion.
• in-degreeequivalent to · In-degree is the number of incoming edges incident to a vertex in a directed graph, optionally measured by the total weight of those edges.
• out-degreeequivalent to · Out-degree is the number of directed edges leaving a vertex in a directed graph.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.