core_numbers_example.m

比较有用的matlab实例

%% Core numbers in MatlabBGL
% This example illustrates the concept of the core number of a vertex.
% Mathematically, the core number of a vertex v is the largest integer c
% such that v has degree > 0 when all vertices of degree < c are removed.
% Equivalently, the core number of vertex v is the largest integer c such
% that v exists in a graph where all degrees are at least c.

%% A simple algorithm
% The beauty of core-numbers is that they arey very intuitive to compute
% and understand.

%% 
% Let's load some data.  This graph comes from the paper with the O(m)
% algorithm to compute the core numbers of an undirected graph by Batagelj
% and Zaversnik, "An O(m) algorithm for the cores decomposition of a
% network."
load '../graphs/cores_example.mat';
%%
% Plot the data.
gplot(A,xy); hold on; plot(xy(:,1), xy(:,2),'r.','MarkerSize',24); hold off;
text(xy(:,1)+0.1, xy(:,2)+0.1, num2str((1:21)'));set(gcf,'Color',[1,1,1]);
set(gca,'XTick',[]);set(gca,'YTick',[]);xlim([-1,10]);ylim([-2,7]);axis off;

%%
% By inspection, vertex 16 is in a 0 core because it has no edges in the
% graph.  
%
% From the statement of the property, let's figure out the core numbers
% for this graph.  For each possible degree d, let's remove all vertices 
% with degree <= d and degree>0 and repeat this until there are no vertices
% with degree (0,d].  Then, any vertex that is left, must have core number
% at least d+1. 
%
% The following code implements that algorithm where the graph Ad is the
% current working version of the graph.
% At the end of the for loop, the graph Ad is the graph A where all 
% vertices of degree <= d have been removed.  
max_deg = full(max(sum(A)));
cn = zeros(num_vertices(A),1);
Ad = A; dv=sum(Ad);          
for d=0:max_deg                
  % while they are vertices with degree in (0,d], remove them
  while any(dv<=d&dv>0), Ad(dv<=d,:)=0;Ad(:,dv<=d)=0;dv=sum(Ad);end
  % any vertex that is left must core number at least d+1;
  cn(dv>d) = d+1;
end
arrayfun(@(v,c) fprintf('core_number(%2i) = %i\n',v,c),1:size(A,1),cn');

%%
% The output shows us that vertex 16 is the only vertex with a core number
% of 0.  Because this graph is an example, "it just so happens" that the
% cores make a nice picture.  The following code plots the convex hull
% around the points inside of a k-core.  The darker the color, the higher
% the core.
clf; hold on; wh=ones(1,3); colors={0.85*wh,0.7*wh,0.55*wh,0.4*wh};
for c=unique(cn')
  m=cn>=c; cl=colors{c+1}; lw=16*1.5^(max(cn)-c);
  xym=xy(m,:);is=convhull(xym(:,1),xym(:,2));
  h=fill(xym(is,1),xym(is,2),cl);set(h,'LineWidth',lw,'EdgeColor',cl);
end
gplot(A,xy,'k-');  plot(xy(:,1), xy(:,2),'r.','MarkerSize',24);
text(xy(:,1)+0.1, xy(:,2)+0.1, num2str((1:21)'));set(gcf,'Color',[1,1,1]);
xlim([-1,10]);ylim([-2,7]);axis off; hold off;

%%
% The figure shows the 0-core, the 1-core, the 2-core and the 3-core.
% Although vertex 11 has degree 5, it is only a 2-core vertex because it
% links to two 1-core vertices.  Also, note that the cores aren't
% necessarily connected components.  The 2-core contains two connected
% components (2-11,14-15) and (17-20).  

%% With MatlabBGL
% The MatlabBGL function core_numbers implements efficient algorithms to
% compute the cores of a graph.  These algorithms are significantly more
% efficient than the previous code and produce identical output.

%%
% Let's check that they produce the same output.
cn_bgl = core_numbers(A);
any(cn_bgl-cn)

%% The core numbers of a road network
% For fun, let's see how many cores there are in a road network.  Vertices
% in a 1-core in a road network have at least one path between them
% (assuming the underlying network is connected).  Vertices in a 2-core
% have at least two paths between them.  
load('../graphs/minnesota.mat');A=spones(A); % convert to unweighted
[cn csz]=core_numbers(A);  cs=unique(cn);
arrayfun(@(v,c) fprintf('core(%2i) = %4i\n',v,c),cs,csz(cs+1));
% Now, you might complain that there are certain vertices in this graph
% that simply chain a path in the road network so it draws correctly.  The
% following code removes all vertices of degree two and connects the
% end-points of the degree two vertex directly.  It applies this prodecure
% iteratively until all the vertices of degree two are gone.  At the end,
% we compute the core nubmers again.
d2v=find(sum(A,2)==2);
while ~isempty(d2v)
    for v=d2v'
        l=find(A(:,v));A(l(1),v)=0;A(l(2),v)=0;A(v,l(1))=0;A(v,l(2))=0;
        A(l(1),l(2))=1;A(l(2),l(1))=1;
    end
    d2v=find(sum(A,2)==2);
end
max(core_numbers(A))

%%
% The highest core is still two!  I think that's pretty amazing.  There
% aren't subnetworks of the Minnesota highways where you always have at
% least three choices at every intersection.