Центральность графа

[Razor]

Вот статься на википедии http://en.wikipedia.org/wiki/Centrality.
Мне, собственно, нужен алгоритм нахождения любой из 4х центральностей ( для неориентированного графа), например, по матрице смежности. Если у кого есть алгоритм, или информация на русском, буду премного благодарен.

[Circiter]

По-моему, по приведенной вами ссылке информации достаточно --- там есть формулы, объяснения, и ссылки, в том числе и на описания алгоритмов. Кстати, вы сказали, что вам нужна любая центральность, вот и реализуйте поиск самой простой, degree centrality. :)

[Razor]

Хм, если разобраться, то там и правда не сложный алгоритм. Спасибо.
А вот если считать betweenness centrality, есть ли какой-нибудь алгоритм нахождения числа кратчайших путей, проходящих через ? Как найти кратчайший путь я понимаю, но мне просто надо сделать из этого программу. И существует ли betweenness centrality для графа, или она только для каждой вершины?

[Razor]

Я нашел алгоритм нахождения кратчайших расстояний между 2 вершинами. http://e-maxx.ru/algo/floyd_warshall_algorithm - если кому понадобится. А есть ли похожий алгоритм для нахождения кратчайших расстояний, проходящих через заданную вершину?

[Circiter]

Посмотрите на последнем вами указанном ресурсе алгоритмы в разделе "кратчайшие пути из одной вершины", например этот, этот или этот, или даже вот этот. Хотя вам нужен именно тот, которой вы сами нашли (алгоритм Флойда-Уоршола). :) Ещё можно попробовать алгоритм Джонсона.

Но я ещё раз обращаю ваше внимание на ссылки из вики-статьи. Например для betweenness centrality смотрите U.Brandes, A faster algorithm for betweenness centrality.

Также взгляните на используемый самим гуглом eigenvector centrality (краткое описание там же, в вики).

[Razor]

Мне все-таки надо найти betweenness centrality. Статью A faster algorithm for betweenness centrality я уже нашел и думаю над ней продолжительное время. Там написан алгоритм нахождения центральности (именно то, что мне нужно), но не все понятно.
Что есть функция d[] и для чего введена вершина t, если мы ее не используем? И в строке foreach neighbor w of v do под соседом подразумевается, что w и v соединены ребром?

[Circiter]

Цитата:

Что есть функция d[]

Видимо, массив расстояний от текущей вершины $s$ до всех остальных. Я не вникал. :)

Цитата:

для чего введена вершина t

Это просто вспомогательная переменная. Там ведь написано что-то вроде $d[t]\gets -1,\ t\in V$, т.е. расстояния до всех вершин из $V$ полагаются равными минус единице.

Цитата:

под соседом подразумевается, что w и v соединены ребром?

Конечно.

-- Ср июл 07, 2010 04:19:41 --

А вообще, посмотрите готовые реализации, например в библиотеках boost graph library или igraph.

[Razor]

Все-таки реализовал этот алгоритм на с++. Вот, если кому понадобится:

#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <boost\foreach.hpp>
#define foreach BOOST_FOREACH

using namespace std;

void Erase(queue<int> A)
{
   while(!A.empty())
      A.pop();
}
void Erase(stack<int> A)
{
   while(!A.empty())
      A.pop();
}
class BetweennessData 
{
public:
   double d;
   double sigma;
   vector<int> p;
   double delta;

   BetweennessData() 
   {
      d = -1;
      sigma = 0;
      delta = 0;
      p.clear();
   }
};
int main()
{
   int size = 4;
   double* Cb = new double[size];
   int **Adj;
   Adj = new int *[size];
   for(int i  = 0; i<size; i++)
   {
      Adj[i]=new int[size];
   }
   Adj[0][0]=0; Adj[0][1]=1;Adj[0][2]=0; Adj[0][3]=1;
   Adj[1][0]=1; Adj[1][2]=0;Adj[1][2]=1; Adj[1][3]=0;
   Adj[2][0]=0; Adj[2][1]=1;Adj[2][2]=0; Adj[2][3]=1;
   Adj[3][0]=1; Adj[3][2]=0;Adj[3][2]=1; Adj[3][3]=0;
   for (int i = 0; i<size; i++)
   {
      Cb[i]=0;
   }
   stack<int> S;
   map<int,vector<int>> P;
   queue<int> Q;
   map<int, BetweennessData> decorator;
   for( int s = 0; s<size; s++ )
   {
      decorator.clear();
      Erase(S);
      P.clear();
      Erase(Q);
      decorator[s].sigma = 1;
        decorator[s].d = 0;
      Q.push(s);

      while (!Q.empty())
      {
         int v = Q.front();
         Q.pop();
         S.push(v);

         for (int w = 0; w<size; w++)
         {
            if(Adj[v][w]>0)
            {
               // w found for the first time?

               if (decorator[w].d < 0)
               {
                  Q.push(w);
                  decorator[w].d = decorator[v].d + 1;
               }

               // Shortest path to w via v?

               if (decorator[w].d == decorator[v].d + 1)
               {
                  decorator[w].sigma += decorator[v].sigma;
                  decorator[w].p.push_back(v);
               }
            }
         }
      }
      while (!S.empty())
      {
         int w = S.top();
         S.pop();
         foreach(int v,decorator[w].p)
         {
            decorator[v].delta +=(decorator[v].sigma /decorator[w].sigma )* ( 1.0 + decorator[w].delta );
         }
         if (w != s)
         {
            Cb[w]+=decorator[w].delta;
         }
      }
   }
   for (int i = 0; i<size; i++)
   {
      Cb[i]/=2;
      cout << Cb[i] << endl;
   }
   system("pause");
   return 0;
}