My Math Forum graph theory - social networks and reverting the graph

 Applied Math Applied Math Forum

 December 28th, 2010, 02: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 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: 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

### content

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lubna_mira Applied Math 0 January 12th, 2014 01:52 PM avnerg Applied Math 0 September 18th, 2013 06:03 AM kec11494 Applied Math 0 December 14th, 2010 06:01 PM davy89 Applied Math 1 November 30th, 2008 01:05 PM davy89 Computer Science 1 November 22nd, 2008 02:58 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top