Analysis of weighted networks.

By Mark Newman. 2004

2,481 citations recorded by the source corpus.

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 simple proof of the maximum-flow-minimum-cut theorem.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, methodology): “Modularity can be easily extended to graphs with weighted edges (Newman, 2004).”
UserRec: A User Recommendation Framework in Social Tagging Systems (2010, methodology): “The generated undirected weighted tag-graph is mapped to an undirected unweighted multigraph based on (Newman 2004).”
Motif-based communities in complex networks (2007, background): “The formula also holds for weighted networks, which can be inferred from the mapping between weighted networks and unweighted multigraphs [3].”
Latent social structure in open source projects (2008, methodology): “adapting binary network algorithms to work on weighted networks [49], we modified our social networks by introducing one edge between each pair of nodes per email sent between them (i.”
What do centrality measures measure in psychological networks? (2019, background): “As Figure 1 is a weighted network, one could also, instead of just counting if there is an edge or not, take the edge weights into account, which is known as strength centrality (Barrat, Barthelemy, Pastor-Satorras, & Vespignani, 2004; Newman, 2004).”
Node centrality in weighted networks: Generalizing degree and shortest paths (2010, background): “Degree has generally been extended to the sum of weights when analyzing weighted networks (Barrat et al., 2004; Newman, 2004; Opsahl et al., 2008), and labeled node strength.”
Linear and Multilinear Algebra (2007, background): “D ow nl oa de d By : [ Bu ga lic ia 2 00 7] A t: 06 :1 6 9 M ar ch 2 00 7 communicating between node pairs [12].”
Network-Based Functional Regions (2011, methodology): “In practice, this problem has been shown to be computationally hard, and therefore some form of heuristic is required to approximate modularity maximisation (Newman, 2004a; 2006b).”
Identification of influencers - Measuring influence in customer networks (2008, background): “into a multigraph, where the same pair of vertices can be connected by multiple edges (Newman 2004).”
Multilayer networks (2013, background): “, “weights”) [21, 241,350], exist only between nodes that belong to different sets (e.”
Spanning Tree Based Community Detection Using Min-Max Modularity (2016, neutral): “QUnrelated−pair = 1 2(nC2 − m − α) ∑ 1≤i, j≤m (Ai j − Ec i j)δ(Ci,C j) (7)”
A socio-aware overlay for publish/subscribe communication in delay tolerant networks (2007, methodology): “For SIMPLE, we show both its comparison with the centralised k-CLIQUE (.rst) and the centralised Newman method [22] (second).”