My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
December 28th, 2010, 02:49 PM   #1
Joined: Dec 2010

Posts: 1
Thanks: 0

graph theory - social networks and reverting the graph


I'd like to implement algorithm of Newman-Girvan but I've got some difficulties.

Summary of my problem: As far as I know, Newman-Girvan 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 Newman-Girvan algorithm. The goal of detecting community structure is to make logical and good division into those subgroups.

How the Newman-Girvan 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. Breadth-first 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 breadth-first 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:

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!
johnyjj2 is offline  

  My Math Forum > College Math Forum > Applied Math

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 01:52 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
Graph theory - 4 stroke graph kec11494 Applied Math 0 December 14th, 2010 06:01 PM
Graph Theory davy89 Applied Math 1 November 30th, 2008 01:05 PM
Graph theory 3 davy89 Computer Science 1 November 22nd, 2008 02:58 PM

Copyright © 2019 My Math Forum. All rights reserved.