# [2021-01-12] [CS224W] Motifs and Structural Roles in Networks

** Published:**

# Subgraphs, Motifs

Network motifs: recurring, significant patterns of interconnections

- induced subgraphs - consider all edges connecting pairs of vertices in subset
- recurrence - allow overlapping of motifs
- signficance of a motif: Motifs are overrepresented in a network when compared to randomized networks

How to get the randomized networks? Configuration model: : Generate a random graph with a given degree sequence k1, k2, … kN ( the same degree as the real network) Each $G^{rand}$ has the same #(nodes), #(edges) and #(degree distribution) as $G^{real}$

- Spokes: Nodes with spokes; randomly pair up mini-nodes
- Swithing: Select a pair of edges A->B, C->D at random; Exchange the endpoints to give A->D, C->B

# Graphlets

Definition: connected non-isomorphic subgraphs Graphlet degree vector counts #(graphlets) that a node touches at a particular orbit (takes into account the symmetries of a subgraph) Graphlet degree vector provides a measure of a node’s local network topology

# Structural Roles in Networks

Role: A collection of nodes which have similar positions in a network Structural equivalence: Nodes u and v are structurally equivalent if they have the same relationships to all other nodes

# Structure Role Discovery Method - RoIX

Recursive feature extraction turns network connectivity into structural features. Use the neighborhood features to generate new recursive features.

- Neighborhood features:
- Local features: all measures of the node degreee (in-, out- degree, total degree, etc.)
- Egonet features: Egonet includes the node, its neighbors, and any edges in the induced subgraph on these nodes. #(within egonet edges), #(edges entering/leaving egonet)

- recursive features:
- Use the set of current node features to generate additional features; Two types of aggregate functions: mean and sum