Aller au contenu

Fichier:Centrality.svg

Le contenu de la page n’est pas pris en charge dans d’autres langues.
Une page de Wikipédia, l'encyclopédie libre.

Fichier d’origine ‎(Fichier SVG, nominalement de 600 × 900 pixels, taille : 476 kio)

Ce fichier et sa description proviennent de Wikimedia Commons.

Accéder au fichier sur Commons

?
L’exactitude de cette description est remise en cause.
Raison : S’il vous plaît voir la discussion pertinente sur la page de discussion.

Description

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 Travail personnel
Auteur Claudio Rocchini

Conditions d’utilisation

Moi, en tant que détenteur des droits d’auteur sur cette œuvre, je la publie sous la licence suivante :
w:fr:Creative Commons
paternité partage à l’identique
Ce fichier est disponible selon les termes de la licence Creative Commons Attribution – Partage dans les Mêmes Conditions 3.0 (non transposée).
Vous êtes libre :
  • de partager – de copier, distribuer et transmettre cette œuvre
  • d’adapter – de modifier cette œuvre
Sous les conditions suivantes :
  • paternité – Vous devez donner les informations appropriées concernant l'auteur, fournir un lien vers la licence et indiquer si des modifications ont été faites. Vous pouvez faire cela par tout moyen raisonnable, mais en aucune façon suggérant que l’auteur vous soutient ou approuve l’utilisation que vous en faites.
  • partage à l’identique – Si vous modifiez, transformez, ou vous basez sur cette œuvre, vous devez distribuer votre contribution sous la même licence ou une licence compatible avec celle de l’original.

Source Code

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;
}

Légendes

Ajoutez en une ligne la description de ce que représente ce fichier

Éléments décrits dans ce fichier

dépeint

type MIME

image/svg+xml

somme de contrôle

38d8cb93e696c9f13af6b90f6f659fd44d0bbebe

méthode de détermination : SHA-1

taille des données

486 940 octet

hauteur

900 pixel

largeur

600 pixel

Historique du fichier

Cliquer sur une date et heure pour voir le fichier tel qu'il était à ce moment-là.

Date et heureVignetteDimensionsUtilisateurCommentaire
actuel15 novembre 2012 à 17:01Vignette pour la version du 15 novembre 2012 à 17:01600 × 900 (476 kio)RocchiniUser created page with UploadWizard

La page suivante utilise ce fichier :

Usage global du fichier

Les autres wikis suivants utilisent ce fichier :

Métadonnées

Ce fichier contient des informations supplémentaires, probablement ajoutées par l'appareil photo numérique ou le numériseur utilisé pour le créer.

Si le fichier a été modifié depuis son état original, certains détails peuvent ne pas refléter entièrement l'image modifiée.

Ce document provient de « https://fr.wikipedia.org/wiki/Fichier:Centrality.svg ».