CS224W_Lecture 3 Motifs and Structural Roles in Networks.

 

 

Contents

1. Motif Motivation

2. Network Motif

3. Pysic power of Jure

4. Graphlets : Node Feature Vectors ( Extention of MOtifs)

5. How to find Motifs and Graphlets (ESU Algorithm)

6. Structural Roles in Networks

7. Discovering Structural Roles in the Network ( RolX Method)

 

*subnetwork

subnetworks or subgraphs are the building block of networks 

-> They have the power to characterize and discriminate networks

 

* Network signifance profile

-> Networks from the some domain have similar signifance profiles

 

* Why Do we need motifs ?

Motifs

- help us understand how networks work

- help us predict operation and reaction of the network in a given situtation

 

* Examples

- Feed - forward - loops  ( as like Residual mechanism )

x -> y -> Z 

 

왼쪽부터 feed-foward loops ,  Parallel loops , single-input modules

- feed-forward loops

found in networks of neurons, where they neutralized 'biological noise'

 

- parallel loops

found in food webs

 

- single-input moduels

found in gene control networks

# Signifiance of motifs

key idea ; subgraphs that occur in a real network much more of than in a random newtork have functional signifance

 

 

 

Configuration Model

Goal ; Generate a random graph with a given sequence degree sequence k_1 k_2 … k_n

 

# Graphlets ; Node feature vectors 

; Connected non-isomorphic subgraphs 

* induced subgraphs of any frequency

 

 counting subgraph , subgraph 를 counting 하기 위한 algorithm ESU , pseudo code 

 

# Graph Isomorphism

 

# Structural Role Discovery Method

 

# RoIX : Approach Overview

Node x Role Matrix

- discover the roles 

Role x Feature Matrix

- discover assign features to the roles 

 

 

 

 

## Key points at this lecture 3 

 

# Subgraphs:

- Defining Motifis and graphlets

- Finding Motifs and graphlets

 

# Structural roles in networks

- RoIX: Structural Role Discovery Method

 

# Discovering strucutral roles and its applications:

- Structural simliarity

- Role generalization and transfer learning

- Making sense of roles

 

 

## Recap

# motifis , graphlets benefits how capture the difference between random graph and real graph 

 

# approachs counting subgraphs , at this lecture we learn the algorithms called 'ESU-Tree'

 

# Structrual roles and distinguish them for extraction node feature by 'ROIX approach'