%0 Journal Article %1 citeulike:281 %A Newman, M. E. J. %D 2004 %J Physical Review E %K community %T Analysis of weighted networks %U http://arxiv.org/abs/cond-mat/0407503 %V 70 %X The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a new and simple proof of the max-flow/min-cut theorem.

@article{citeulike:281, abstract = {The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a new and simple proof of the max-flow/min-cut theorem.}, added-at = {2006-09-25T12:54:00.000+0200}, author = {Newman, M. E. J.}, biburl = {https://www.bibsonomy.org/bibtex/26c49ef22fc1fd4fbaeefefe79fa500d6/grahl}, citeulike-article-id = {281}, comment = {especially for weighted graphs --- idea: interpret (non-negrative) weighted graph as multi-edge graphs, then apply standard GN-Algorithm It turns out that one just has to divide the edge betweenness with the edge weight and proceed as usual. They also provide an adopted modularity measure for evaluating if there is a remaining community structure in the graph. (see p7 left eq 8,9 with Aij as the edge weight.) --- "Recently, Girvan and Newman [27] proposed an algo- rithm for community structure discovery in unweighted networks that avoids these drawbacks and appears to work well for many kinds of networks. Since the pub- lication of that work, the author has been asked a num- ber of times whether an appropriate generalization of the algorithm exists for weighted networks. Certainly the al- gorithm can be applied to such networks by simply ignor- ing edge weights, but, as we have argued in this paper, to do so is to throw away useful information contained in the weights, information that could help us to make a more accurate determination of the communities. In this section we use the techniques discussed in this paper to derive an appropriate generalization of the algorithm of Girvan and Newman to weighted networks." "Another and simpler way of summarizing this algo- rithm is the following: we calculate the betweennesses of all edges in our weighted graph in the normal way, ignor- ing the weights. Then we divide each such betweenness by the weight of the corresponding edge, remove the edge with the highest resulting score, recalculate the between- nesses, and repeat. We have derived this algorithm here only for the case of integer weights on the edges, but we can extend it to the non-integer case using the same trick that we employed in Section IIB, of defining successively smaller units in which the weight of an edge is measured. The resulting algorithm is identical to that for the inte- ger case: betweennesses are simply divided by the weight of the edge and the edge with the highest resulting score removed from the network. This algorithm is simple, it is almost as fast as the original unweighted version (adding only the extra op- eration of division by the edge weight), and, as we now show, appears to work excellently."}, eprint = {cond-mat/0407503}, interhash = {5e36ff53e9fd2c58615a38b5ef708a19}, intrahash = {6c49ef22fc1fd4fbaeefefe79fa500d6}, journal = {Physical Review E}, keywords = {community}, month = {November}, priority = {4}, timestamp = {2006-09-25T12:54:00.000+0200}, title = {Analysis of weighted networks}, url = {http://arxiv.org/abs/cond-mat/0407503}, volume = 70, year = 2004 }