BNPgraph package: demo_sparse

This Matlab script shows empirically the sparsity properties of a range of graph models.

For downloading the package and information on installation, visit the BNPgraph webpage.

Reference: F. Caron and E.B. Fox. Sparse graphs using exchangeable random measures. arXiv:1401.1137, 2014.

Author: François Caron, University of Oxford

Tested on Matlab R2014a.

Contents

General settings

clear all

% Add paths
addpath('./GGP/');
addpath('./utils/');

% Save plots and workspace
saveplots = false;
saveworkspace = false;
if saveplots
    rep = './plots/';
    if ~isdir(rep)
        mkdir(rep);
    end
end

% Set the seed
rng('default')

Definition of the graph models

% Model 1: Erdos-Renyi
p = .05;
obj{1} = graphmodel('ER', 100, p);
field{1} = 'n'; % field whose value changes
trial{1} = 2:1:600;
n_samples{1} = 1;
optionrnd{1}={};
% Model 2: Barabasi-Albert
obj{2} = graphmodel('BA', 10);
field{2} = 'n'; % field whose value changes
trial{2} = 2:1:600;
n_samples{2} = 1;
optionrnd{2}={};
% Model 3: Lloyd
sig = 0.1; c = 10; d = 1;
obj{3} = graphmodel('Lloyd', 100, sig, c, d);
field{3} = 'n';
trial{3} = floor(2.^(1:.2:7));
n_samples{3} = 10;
optionrnd{3}={};
% Model 4: GGP (sigma=0)
alpha = 100; tau = 2; sigma = 0;
obj{4} = graphmodel('GGP', alpha, sigma, tau);
field{4} = 'alpha';
trial{4} = 1:.5:130;%5000, tau=5
n_samples{4} = 1;
optionrnd{4}=1e-10;
% Model 5: GGP (sigma=0.5)
alpha = 100; tau = 2; sigma = 0.5;
obj{5} = graphmodel('GGP', alpha, sigma, tau);
field{5} = 'alpha';
trial{5} = 1:.05:40;
n_samples{5} = 1;
optionrnd{5}=1e-5;%-5
% Model 6: GGP (sigma=0.8)
alpha = 100; tau = 2; sigma = 0.8;
obj{6} = graphmodel('GGP', alpha, sigma, tau);
field{6} = 'alpha';
trial{6} = 1:.05:40;
n_samples{6} = 1;
optionrnd{6}=1e-4;%-4

Sample graphs of various sizes

for k=1:length(obj) % For different models
    fprintf('--- Model %d/%d: %s ---\n', k, length(obj), obj{k}.name)
    for i=1:length(trial{k}) % Varying number of nodes
        if rem(i, 100)==0
            fprintf('Trial %d/%d \n', i, length(trial{k}));
        end
        obj{k}.param.(field{k}) = trial{k}(i);
        for j=1:n_samples{k} % For different samples
            G = graphrnd(obj{k}, optionrnd{k}); % Sample the graph
            nbnodes{k}(i,j) = size(G, 1);
            nbedges{k}(i,j) = sum(G(:))/2 + trace(G)/2;
            maxdegree{k}(i,j) = max(sum(G));
            degreeone{k}(i,j) = sum(sum(G)==1);
        end
    end
end
--- Model 1/6: Erdos-Renyi ---
Trial 100/599 
Trial 200/599 
Trial 300/599 
Trial 400/599 
Trial 500/599 
--- Model 2/6: Barabasi-Albert ---
Trial 100/599 
Trial 200/599 
Trial 300/599 
Trial 400/599 
Trial 500/599 
--- Model 3/6: Lloyd ---
--- Model 4/6: Generalized gamma process ---
Trial 100/259 
Trial 200/259 
--- Model 5/6: Generalized gamma process ---
Trial 100/781 
Trial 200/781 
Trial 300/781 
Trial 400/781 
Trial 500/781 
Trial 600/781 
Trial 700/781 
--- Model 6/6: Generalized gamma process ---
Trial 100/781 
Trial 200/781 
Trial 300/781 
Trial 400/781 
Trial 500/781 
Trial 600/781 
Trial 700/781 

Some plots

% Properties of the plots
plotstyles = {'--k', '--+b', '--xc', 'rs', 'rd', 'ro'};
colorstyle = {'k', 'b', [0,0,.6], [1,0,.5], 'r', [.6,0,0]};
leg = {'ER', 'BA', 'Lloyd', 'GGP (\sigma = 0)', 'GGP (\sigma = 0.5)', 'GGP (\sigma = 0.8)'};
set(0,'DefaultAxesFontSize', 12)
set(0,'DefaultTextFontSize', 16)

% Nb of Edges vs nb of nodes on loglog plot
pas = .4;
figure('name', 'edgesvsnodesloglog')
for k=1:length(obj)
    h = plot_loglog(nbnodes{k}(:), nbedges{k}(:), plotstyles{k}, pas);
    set(h,'linewidth', 2, 'markersize', 8, 'markerfacecolor', colorstyle{k},'color', colorstyle{k});
    hold on
end
xlabel('Number of nodes', 'fontsize', 16)
ylabel('Number of edges', 'fontsize', 16)
legend(leg,'fontsize', 16, 'location', 'northwest')
xlim([10, 500])
ylim([10, 20000])
legend('boxoff')
if saveplots
    savefigure(gcf, 'edgesvsnodes', rep);
end
% Nb of Edges/Nb of nodes squared vs nb of nodes on loglog plot
pas = 1;
figure('name', 'edgesvsnodesloglog')
for k=1:length(obj)
    ind = nbnodes{k}(:)>0;
    h = plot_loglog(nbnodes{k}(ind), nbedges{k}(ind)./nbnodes{k}(ind).^2, plotstyles{k}, pas);
    set(h,'linewidth', 2, 'markersize', 8, 'markerfacecolor', colorstyle{k},'color', colorstyle{k});
    hold on
end
xlabel('Number of nodes', 'fontsize', 16)
ylabel('Nb of edges / (Nb of nodes)^2', 'fontsize', 16)
legend(leg,'fontsize', 16, 'location', 'southwest')
xlim([3, 700])
legend('boxoff')
if saveplots
    savefigure(gcf, 'edgesvsnodes2', rep);
end
% Nb of nodes of degree one versus number of nodes
figure('name', 'degonevsnodes');
for k=1:length(obj)
    h = plot_loglog(nbnodes{k}(:), degreeone{k}(:), plotstyles{k}, pas);
    set(h,'linewidth', 2, 'markersize', 8, 'markerfacecolor', colorstyle{k},'color', colorstyle{k});
    hold on
end
xlabel('Number of nodes', 'fontsize', 16);
ylabel('Number of nodes of degree one', 'fontsize', 16);
legend(leg,'fontsize', 16, 'location', 'northwest');
legend('boxoff');
xlim([10, 500])
ylim([1, 2000])
if saveplots
    savefigure(gcf, 'degreeonevsnodes', rep);
end
% Save workspace
if saveworkspace
    save([rep 'test_stats']);
end