Transcript mutual information

Hub Node Detection in
Directed Acyclic Graphs
2008. 3. 11.
Kim, Byoung-Hee
Directions of Future Work on HBN

Algorithm
 Extension from binary-tree type structure to n-ary tree
 Fast and effective learning by hub node detection
 Incorporate features of latent variable models

Theoretical Analysis
 Information compression – efficiency, measurement

Application & Empirical Analysis
 Biological networks – gene regulatory networks, metabolic
networks
 Text
 Social networks
Preliminary Experiment for Detecting
Hub Nodes
s1
sampling
s2
…
s5000
X1
X2
…
X100
Estimation
Structure
Hub nodes
Mutual information /
Conditional MI
• 100 node scale-free/modular BN
• all nodes have binary states

Conjectures
 D-separation vs conditionam mutual information
 d(x, y) > d(x, z) then I(x; y) < I(x; z) asymptotically (mutual information)
 the difference between I(X; Y) and I(X; Y|Z) increases as the degree of Z
increases
 Shortest path vs normalized mutual information
 Data:
5,000 samples out of 100 node networks (1 scale
free and 1 modular)
 d(x, y) > d(x, z) then I(x; y) < I(x; z) asymptotically ????
Shortest Path Length vs NMI - scale free network
Shortest Path Length vs NMI - modular network
1
0.1
0
2
4
6
1
0.1 0
8
10
15
0.01
0.01
0.001
normalized MI
0.001
normalized MI
5
0.0001
1E-05
1E-06
1E-07
0.0001
1E-05
1E-06
1E-07
1E-08
1E-09
1E-08
1E-10
1E-09
1E-11
1E-10
1E-12
shortest path length
shortest path length
20
25
Example 1: some short paths btw
X65 and X86
86
72
65
0.000905
49
0.05604
84
7
0.08434
2
0.0693
0.0759
31
28
I(X65; X86) = 0.082375
1
0.0859
0.0821
0.07947
26
0.0829
17
0.083
I(X65; X86 | Z) =?
Example 2: some short paths btw X7
and X31
0.023
86
72
65
0.0177
0.0183
49
0.0224
84
7
0.0545
2
I(X7; X31) = 0.0194
0.00453
31
I(X7; X31 | Z) = ?
28
1
0.00703
26
0.00754
17
0.0122
0.00895
Experimetns to Verify Conjectures

d(x, y) > d(x, z) then I(x, y) < I(x, z) asymptotically
 Shortest path vs normalized mutual information
 Data:
5,000 samples out of 100 node networks (1 scale
free and 1 modular)
Mutual Information

In probability theory and information theory, the mutu
al information, or transinformation, of two random var
iables is a quantity that measures the mutual depend
ency of the two variables
Updates



Code for the conditional MI has a bug
Couldn’t find any function for calculating MI/cMI in
Matlab and R
‘empirical’ MI/cMI calculation: biased.. Need to
reduce bias