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