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