File:Centrality.svg

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Original file ‎(SVG file, nominally 600 × 900 pixels, file size: 476 KB)

Captions

Captions

Add a one-line explanation of what this file represents
?
The factual accuracy of this description or the file name is disputed.
Reason: Please see the relevant discussion on the talk page.

Summary[edit]

Description
English: Examples of A) Degree centrality, B) Closeness centrality, C) Betweenness centrality, D) Eigenvector centrality, E) Katz centrality and F) Alpha centrality.
Date
Source Own work
Author Claudio Rocchini

Licensing[edit]

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

Source Code[edit]

The source code needs http://www.gnu.org/s/gsl/ . 

/**********************************
 * (C)2012 Claudio Rocchini       *
 *  www.rockini.name              *
 *  CC-BY 3.0                     *
 **********************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <gsl/gsl_matrix.h>
#include <gsl/gsl_linalg.h>
#include <gsl/gsl_eigen.h>
#include "rand.h"

static inline unsigned char f2b( double f ) {
	if(f<0) f = 0; if(f>1) f = 1;
	int i = int(f*256);
	return i<0 ? 0 : i>255 ? 255 : i;
}
 
void HSV2RGB(double h, double s, double v, unsigned char rgb[3] ) {
	if (s == 0) {
		rgb[0] = rgb[1] = rgb[2] = f2b(v);
	} else {
		double v_h = h * 6;
		double v_i = floor(v_h);
		double v_1 = v * (1 - s);
		double v_2 = v * (1 - s * (v_h - v_i));
		double v_3 = v * (1 - s * (1 - (v_h - v_i)));
		double v_r,v_g,v_b;
		if (v_i == 0) {v_r = v;   v_g = v_3; v_b = v_1;}
		else if (v_i == 1) {v_r = v_2; v_g = v;   v_b = v_1;}
		else if (v_i == 2) {v_r = v_1; v_g = v;   v_b = v_3;}
		else if (v_i == 3) {v_r = v_1; v_g = v_2; v_b = v  ;}
		else if (v_i == 4) {v_r = v_3; v_g = v_1; v_b = v  ;}
		else               {v_r = v;   v_g = v_1; v_b = v_2;};

		rgb[0] = f2b(v_r);
		rgb[1] = f2b(v_g);
		rgb[2] = f2b(v_b);
	}
}

class point2 {
public:
	double x,y;
};

double squared_dist( const point2 & p, const point2 & q ) {
	const double dx = p.x - q.x;
	const double dy = p.y - q.y;
	return dx*dx+dy*dy;
}

class edge {
public:
	int a,b;
	edge() {}
	edge( int na, int nb ): a(na),b(nb) {}
};

void floyd_warshall( int NV, const std::vector<edge> & e,
					 std::vector<double> & dist, std::vector<int> & conn ) {
	dist.resize(NV*NV); conn.resize(NV*NV);
	std::fill(dist.begin(),dist.end(),0.0);
	std::fill(conn.begin(),conn.end(),-1);
	std::vector<edge>::const_iterator ie;
	for(ie=e.begin();ie!=e.end();++ie) {
		dist[(*ie).a+NV*(*ie).b] = 1;
		dist[(*ie).b+NV*(*ie).a] = 1;
	}
	for(int k=0;k<NV;++k) for(int i=0;i<NV;++i) for(int j=0;j<NV;++j)
	if((dist[i+NV*k] * dist[k+NV*j] != 0) && (i != j))
		if((dist[i+NV*k] + dist[k+NV*j] < dist[i+NV*j]) || (dist[i+NV*j] == 0)) {
			conn[i+NV*j] = k;
			dist[i+NV*j] = dist[i+NV*k] + dist[k+NV*j];
		}
}

void central_degree( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	std::fill(C.begin(),C.end(),0.0);
	std::vector<edge>::const_iterator i;
	for(i=e.begin();i!=e.end();++i) {
		C[(*i).a] += 1;
		C[(*i).b] += 1;
	}
}

void central_closeness( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	std::vector<double> dist;
	std::vector<int> conn;
	floyd_warshall(NV,e,dist,conn);
	for(int i=0;i<NV;++i) {
		C[i] = 0;
		for(int j=0;j<NV;++j) C[i] += dist[i+NV*j];
		if(C[i]!=0.0) C[i] = 1.0/C[i];
	}
}

void central_betweenness( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	std::vector<double> dist; std::vector<int> conn;
	floyd_warshall(NV,e,dist,conn);
	std::fill(C.begin(),C.end(),0.0);
	for(size_t i=0;i<conn.size();++i)
		if(conn[i]>=0 && conn[i]<NV) C[conn[i]] += 1.0;
	for(size_t j=0;j<C.size();++j) C[j] = log(1+C[j]); // NOTE: the log!
}

void central_eigenvector( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	int i,j;
	gsl_eigen_symmv_workspace * w = gsl_eigen_symmv_alloc(NV);
	gsl_matrix * A    = gsl_matrix_alloc(NV,NV);
	gsl_vector * eval = gsl_vector_alloc(NV);
	gsl_matrix * evec = gsl_matrix_alloc(NV,NV);
	for(i=0;i<NV;++i) for(j=0;j<NV;++j)
		gsl_matrix_set(A,i,j,0.0); 
	for(std::vector<edge>::const_iterator ei=e.begin();ei!=e.end();++ei) {
		gsl_matrix_set(A,(*ei).a,(*ei).b,1.0);
		gsl_matrix_set(A,(*ei).b,(*ei).a,1.0);
	}
	gsl_eigen_symmv(A,eval,evec,w);
	int maxj = 0; double maxv = gsl_vector_get(eval,0);
	for(j=1;j<NV;++j)
		if(maxv<gsl_vector_get(eval,j)) {
			maxv = gsl_vector_get(eval,j);
			maxj = j;
		}
	for(i=0;i<NV;++i)
		C[i] = log(gsl_matrix_get(evec,i,maxj));	// NOTE: the log!
	gsl_matrix_free(evec);
	gsl_vector_free(eval);
	gsl_matrix_free(A);
	gsl_eigen_symmv_free(w);
}

void central_katz( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	const double alpha = 0.5;
	std::vector<double> dist; std::vector<int> conn;
	floyd_warshall(NV,e,dist,conn);
	for(int i=0;i<NV;++i) {
		C[i] = 0.0;
		for(int j=0;j<NV;++j) if(i!=j)
			C[i] += pow(alpha,dist[i+NV*j]);
	}
}

void central_alpha( int NV, const std::vector<edge> & e, std::vector<double> & C ) {
	const double alpha = 0.1;
	int i,j;
	gsl_matrix * A    = gsl_matrix_alloc(NV,NV);
	for(i=0;i<NV;++i) for(j=0;j<NV;++j)
		gsl_matrix_set(A,i,j,0.0); 
	for(std::vector<edge>::const_iterator ei=e.begin();ei!=e.end();++ei) {
		gsl_matrix_set(A,(*ei).a,(*ei).b,1.0);
		gsl_matrix_set(A,(*ei).b,(*ei).a,1.0);
	}
	for(i=0;i<NV;++i) for(j=0;j<NV;++j) {
		double t = -alpha*gsl_matrix_get(A,i,j);
		if(i==j) t += 1.0;
		gsl_matrix_set(A,i,j,t);
	}
	gsl_vector * x = gsl_vector_alloc(NV);
	gsl_vector * b = gsl_vector_alloc(NV);
	for(i=0;i<NV;++i) gsl_vector_set(b,i,1.0);
	gsl_linalg_HH_solve(A,b,x);
	for(i=0;i<NV;++i) C[i] = gsl_vector_get(x,i);
	gsl_vector_free(b);
	gsl_vector_free(x);
	gsl_matrix_free(A);
}

void central( int NV, const std::vector<edge> & e, std::vector<double> & C, double & minv, double & maxv, int m )  {
	C.resize(NV);
	switch(m) {
	case 0: central_degree(NV,e,C); break;
	case 1: central_closeness(NV,e,C); break;
	case 2: central_betweenness(NV,e,C); break;
	case 3: central_eigenvector(NV,e,C); break;
	case 4: central_katz(NV,e,C); break;
	case 5: central_alpha(NV,e,C); break;
	}
	minv = maxv = C[0];
	for(int i=1;i<NV;++i) {
		if(minv>C[i]) minv = C[i];
		if(maxv<C[i]) maxv = C[i];
	}
}

int main() {
	const int N = 256;
	const int NR = 3;
	const int NC = 2;
	const double SS = 300;
	const double SX=SS*NC, SY=SS*NR;
	const double R=5, B=6;
	const double MD2=(0.03)*(0.03),D2=(0.1)*(0.1);
	int i,j;
	point2 pts[N];

	for(i=0;i<N;++i)
		do {
			pts[i].x = DRand();
			pts[i].y = DRand();
			for(j=0;j<i;++j) if(squared_dist(pts[i],pts[j])<MD2) break;
		} while(j<i);

	std::vector<edge> edges;
	for(i=0;i<N-1;++i) for(j=i+1;j<N;++j)
		if(squared_dist(pts[i],pts[j])<D2) 
			edges.push_back(edge(i,j));
	
	FILE * fo = fopen("central.svg","w");
	fprintf(fo,
		"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
		"<svg xmlns:svg=\"http://www.w3.org/2000/svg\" xmlns=\"http://www.w3.org/2000/svg\"\n"
		"version=\"1.0\" width=\"%g\" height=\"%g\" id=\"central\">\n"
		,SX,SY
	);
	
	for(int ir=0;ir<NR;++ir) {
		for(int ic=0;ic<NC;++ic) {
			std::vector<double> C;
			double minv,maxv;
			central(N,edges,C,minv,maxv,ic+NC*ir);
	 
			fprintf(fo,"<g style=\"stroke:#000000;stroke-width:1;stroke-linejoin:round;fill:none\">\n");
			for(i=0;i<int(edges.size());++i)
				fprintf(fo,"<line x1=\"%6.2f\" y1=\"%6.2f\" x2=\"%6.2f\" y2=\"%6.2f\"/>\n"
					,SX*ic/NC + (SX/NC-B*2)*pts[edges[i].a].x
					,SY*ir/NR + (SY/NR-B*2)*pts[edges[i].a].y
					,SX*ic/NC + (SX/NC-B*2)*pts[edges[i].b].x
					,SY*ir/NR + (SY/NR-B*2)*pts[edges[i].b].y
				);
			fprintf(fo,"</g>\n");
			for(i=0;i<N;++i) {
				unsigned char rgb[3];
				HSV2RGB( (2*(maxv-C[i]))/(3*(maxv-minv)),0.9,1.0,rgb);
				fprintf(fo,"<circle cx=\"%6.2f\" cy=\"%6.2f\" r=\"%6.2f\" style=\"stroke:#000000;"
				           "stroke-width:0.5;stroke-linejoin:round;fill:#%02X%02X%02X\"/>\n"
					,SX*ic/NC + (SX/NC-B*2)*pts[i].x
					,SY*ir/NR + (SY/NR-B*2)*pts[i].y
					,R
					,rgb[0],rgb[1],rgb[2]
				);
			}
		}
	}
	fprintf(fo,"</svg>\n");
	fclose(fo);
	return 0;
}

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current15:01, 15 November 2012Thumbnail for version as of 15:01, 15 November 2012600 × 900 (476 KB)Rocchini (talk | contribs)User created page with UploadWizard

You cannot overwrite this file.

There are no pages that use this file.

File usage on other wikis

The following other wikis use this file:

Metadata

This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:Centrality.svg&oldid=852627927"