-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathReadme.txt
82 lines (54 loc) · 3.05 KB
/
Readme.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
================================================
Stochastic Blockmodel Approximation of a Graphon
================================================
This MATLAB package is a supplement to the paper
E. M. Airoldi, T. B. Costa, and S. H. Chan, "Stochastic blockmodel approximation of a graphon: Theory and consistent estimation", Advances in Neural Information Processing Systems 2013.
================================================
Content:
1. Construct Graphs from a Graphon
Method 1: [G P u] = construct_a_graph(w,n,T)
Input: w - a Graphon
n - number of nodes
T - number of observations
Output: G - graph (size nxnxT)
P - probability of each node
u - label indices
Method 2: G = construct_a_graph_from_P(P,n,T)
Input: P - probability of each node
n - number of nodes
T - number of observations
Output: G - graph (size nxnxT)
2. Stochastic Blockmodel Approximation
Step 1: B = estimate_blocks_directed(G,Delta)
Input: G - graph
Delta - the threshold parameter (see Demo_Crossvalidation.m)
Output: B - clusters/blocks
Step 2: [H,P] = histogram3D(G,B)
Input: G - graph
B - estimated clusters/blocks
Output: H - estimated histogram
P - estimated probability of each node (ie graphon)
(remark, the estimated P is *not* canonical)
3. Cross validation
Please check Demo_crossvalidation.m
4. Results reported in the paper
Fig2a.m Mean Absolute Error vs Number of Nodes
Fig2b.m Mean Absolute Error vs Number of Observations
Fig3a.m Mean Absolute Error vs Number of Blocks
Fig3b.m Mean Absolute Error vs Percentage of Missing Links
Fig4 Mean Absolute Error for two types of graphons
5. Compared Methods
(i) Largest Gap [1] (estimate_blocks_largest_gap.m)
(ii) Universal Singular Value Thresholding [2] (Method_chatterjee.m)
(iii) Matrix Completion [3] (Method_matrix_completion.m)
References
[1] A. Channarond, J. Daudin, and S. Robin. Classification and estimation in the Stochastic Blockmodel based on the empirical degrees. Electronic Journal of Statistics, 6:2574–2601, 2012.
[2] S. Chatterjee. Matrix estimation by universal singular value thresholding. ArXiv:1212.1247. 2012.
[3] R.H. Keshavan, A.Montanari, and S. Oh. Matrix completion from a few entries. IEEE Trans. Information Theory, 56:2980–2998, Jun. 2010.
================================================
COPYRIGHT (C) 2013 Edoardo Airoldi, Thiago Costa, Stanley Chan
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.
================================================
Last update: November 17, 2013