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

1 minute read


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


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