Transcript Network Motifs - Computer Science

Network Motifs
Zach Saul
CS 289
Network Motifs: Simple Building Blocks of Complex Networks
R. Milo et al.
Network Models
• Interactions are represented as directed
nodes (as presented in class)
• Example problems include gene networks,
neural nets, ecological models and
computer networking models
Network Motifs
• Patterns that appear more often in real
networks than in randomly generated
networks
• Many notions of a random network
– Naïve algorithm
– Erdos-Renyi random graphs
– Scale free networks
– Even more specialized?
Random Graphs
• Three node motifs
– Preserve degree for each node
• Four node motifs
– Preserve degree for each node
– Preserve the number of three node motifs
Example Motif
Method
• Using brute force, searched target network for
every possible subgraph, counting results
• Similarly, searched random network
• Motifs are patterns that occur greater or equal
number of times in random networks more than
1% of the time.
Results
Results (cont.)
Gene/Neural Net Analysis
• The nematode neural net and the gene net
both contain similar structures
– Feed forward
– Bi-fan
• Both are information processing networks
with sensory and acting components
– Sensory neurons/transcription factors
regulated by biochemical signals
– Motor neurons/structural genes
Food Web Analysis
• Food Webs do not show feed-forward
motifs
– Suggests that direct interaction between
species at a separation of two layers selected
against (e.g. Omnivores)
• Bi-parallel suggests that prey of same
predator share prey
Electronic Circuit Analysis
• Circuits can be classified by function using
network motifs
• Circuits from benchmark set showed
different motifs for each functional class
• Some info processing circuits show similar
motifs to biological info processing circuits
Web Analysis
• Network of hyperlinks
• Many more bidirectional links
• Motifs indicate a design that allows the
shortest path among sets of related pages
Conclusions
• Technique robust to data errors
• Motifs can indicate common function
• ..or could indicate similar evolutionary
constraints
• Scalability to other types of networks
possible
• Scalability to larger subgraphs difficult