
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 28th, 2010, 03:49 PM  #1 
Newbie Joined: Dec 2010 Posts: 1 Thanks: 0  graph theory  social networks and reverting the graph
Hello, I'd like to implement algorithm of NewmanGirvan but I've got some difficulties.  Summary of my problem: As far as I know, NewmanGirvan algorithm requires changing graph with nodes and vertices to such a graph in which nodes and vertices are reversed. If that's right, how can I change one graph to the other. If that's not right, why am I mistaken or how can I avoid it?  Summary of detecting community structure: I've got a graph containing edges (i.e. people) and vertices (i.e. connections between people). In the community some people know other people but it cannot be stated that everybody knows everybody. These relations can be written as symmetric matrix n by n in which main diagonal doesn't matter. It is possible that in the community of e.g. 50 people, there are two subcommunities, e.g. 15 people and 35 people. Inside each of subcommunities people know other people from the same subcommunity well, but they don't know any people from the other subcommunity, with some little exceptions. In other words connections between two subgroups are much more between than connections inside the groups. This idea of betweenness is crucial for NewmanGirvan algorithm. The goal of detecting community structure is to make logical and good division into those subgroups. How the NewmanGirvan algorithm work (according to "Finding and evaluating community structure in networks" by Newman & Girvan, page no. 4): 1. Calculate betweenness scores for all edges in the network. 2. Find the edge with the highest score and remove it from the network. 3. Recalculate betweenness for all remaining edges. 4. Repeat from step 2. The crucial thing in the algorithm above is how to calculate betweenness. I like explaining algorithms in the form of processes with well defined input and output. This is crucial from the point of view of implementing it in computer programming language because first thing which I'd like to do is to create proper classes and their variables (matrices and so on). The algorithm of calculating the betweenness (page no. 5 in "Finding..."): I. Breadthfirst search (starting at vertex s) a) input  matrix n by n (edges and vertices are reversed!) which says (as boolean value) which vertex is connected with each other by edges b) output  two vectors (distances and weights) on vertices II. Calculating the total betweenness a) input  weights (on vertices) and matrix n by n b) output  matrix n by n (we may call it 'success' matrix) which says (after repeating the process for all n source vertices s) what resulting scores on the edges are; we can sum those and find total betweenness for all the edges If I understood it properly, in the above algorithm for calculating the betweenness, I need to supply as the input for breadthfirst search, matrix in which edges and vertices are reversed. I think so because there is also an example (page 5, figure 4) with some examplary graphs. In those graphs vertices are shown as points and edges are connections between vertices. At the top there is point indicating vertex s. So I have tried to think how to change graph with edges connected with vertices to the opposite one. By first graph I consider matrix n by n with zeroes or ones to indicate if somebody knows the other person (if rows and columns are edges and boolean values indicate connections, i.e. vertices). After short consideration it looks for me that the second matrix (after transformation) is bigger than the first one. What I need is algorithm which would allow me to transform one graph (matrix) to the other, i.e. to reverse edges and vertices. I have tried to analyse this problem myself and I haven't found any final solution. Some very basic attempts to solve this problem are shown here: http://images37.fotosik.pl/466/084971fb37060c55.jpg I don't really know if it is allowed, according to the licence, to upload the file with "Finding..." by Newman and Girvan here. If it is, I can upload it and supply the link for this file. Thanks you for your help in advance! Regards! 

Tags 
graph, networks, reverting, social, theory 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 02:52 PM 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 07:03 AM 
Graph theory  4 stroke graph  kec11494  Applied Math  0  December 14th, 2010 07:01 PM 
Graph Theory  davy89  Applied Math  1  November 30th, 2008 02:05 PM 
Graph theory 3  davy89  Computer Science  1  November 22nd, 2008 03:58 PM 