Weighted network

Last updated

A weighted network is a network where the ties among nodes have weights assigned to them. A network is a system whose elements are somehow connected. [1] The elements of a system are represented as nodes (also known as actors or vertices) and the connections among interacting elements are known as ties, edges, arcs, or links. The nodes might be neurons, individuals, groups, organisations, airports, or even countries, whereas ties can take the form of friendship, communication, collaboration, alliance, flow, or trade, to name a few.

Contents

In a number of real-world networks, not all ties in a network have the same capacity. In fact, ties are often associated with weights that differentiate them in terms of their strength, intensity, or capacity [2] [3] On the one hand, Mark Granovetter (1973) [4] argued that the strength of social relationships in social networks is a function of their duration, emotional intensity, intimacy, and exchange of services. On the other, for non-social networks, weights often refer to the function performed by ties, e.g., the carbon flow (mg/m2/day) between species in food webs, [5] the number of synapses and gap junctions in neural networks, [6] or the amount of traffic flowing along connections in transportation networks. [7]

Example of a weighted network (weights can also be visualized by giving edges different widths) Weighted network.svg
Example of a weighted network (weights can also be visualized by giving edges different widths)

By recording the strength of ties, [8] a weighted network can be created (also known as a valued network).

Weighted networks are also widely used in genomic and systems biologic applications. [3] For example, weighted gene co-expression network analysis (WGCNA) is often used for constructing a weighted network among genes (or gene products) based on gene expression (e.g. microarray) data. [9] More generally, weighted correlation networks can be defined by soft-thresholding the pairwise correlations among variables (e.g. gene measurements). [10]

Measures for weighted networks

Although weighted networks are more difficult to analyse than if ties were simply present or absent, a number of network measures has been proposed for weighted networks:

A theoretical advantage of weighted networks is that they allow one to derive relationships among different network measures (also known as network concepts, statistics or indices). [3] For example, Dong and Horvath (2007) [15] show that simple relationships among network measures can be derived in clusters of nodes (modules) in weighted networks. For weighted correlation networks, one can use the angular interpretation of correlations to provide a geometric interpretation of network theoretic concepts and to derive unexpected relationships among them Horvath and Dong (2008) [16]

Intrinsically dense weighted networks

In network theory, intrinsically dense weighted networks represent a distinctive class of complex structures characterized by a near-completeness of links and associated weights, transcending the conventional constraints of sparser network configurations. Unlike sparse networks where the absence of links typically indicate lack of interaction, intrinsically dense networks exhibit a comprehensive interconnection among nodes, where each node is intricately linked to all others. Such systems do not have obvious natural limits for a node to have connection with any or all of the other nodes.

The term "intrinsically dense" emphasizes that edges within these networks may not solely represent positive relationships but can encompass randomness or even negative associations based on their respective weights. For instance, in scenarios where edge weights denote similarity between nodes, lower weights don't just signify a lack of similarity but may connote dissimilarity or negative underlying links. The study by Gursoy & Badur (2021) [17] introduced methods to extract meaningful and sparse signed backbones from these networks, showcasing their significance in preserving the intricate structures inherent in intrinsically dense weighted networks across various domains including certain migration, voting, human contact, and species cohabitation networks. This distinctive network paradigm expands the understanding of complex systems observed in natural, social, and technological domains, offering insights into nuanced interactions and relationships within these densely interconnected networks.

Software for analysing weighted networks

There are a number of software packages that can analyse weighted networks; see social network analysis software. Among these are the proprietary software UCINET and the open-source package tnet. [18]

The WGCNA R package implements functions for constructing and analyzing weighted networks in particular weighted correlation networks. [10]

See also

Related Research Articles

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Social network analysis</span> Analysis of social structures using network and graph theory

Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of nodes and the ties, edges, or links that connect them. Examples of social structures commonly visualized through social network analysis include social media networks, meme spread, information circulation, friendship and acquaintance networks, peer learner networks, business networks, knowledge networks, difficult working relationships, collaboration graphs, kinship, disease transmission, and sexual relationships. These networks are often visualized through sociograms in which nodes are represented as points and ties are represented as lines. These visualizations provide a means of qualitatively assessing networks by varying the visual representation of their nodes and edges to reflect attributes of interest.

<span class="mw-page-title-main">Gene regulatory network</span> Collection of molecular regulators

A generegulatory network (GRN) is a collection of molecular regulators that interact with each other and with other substances in the cell to govern the gene expression levels of mRNA and proteins which, in turn, determine the function of the cell. GRN also play a central role in morphogenesis, the creation of body structures, which in turn is central to evolutionary developmental biology (evo-devo).

<span class="mw-page-title-main">Network theory</span> Study of graphs as a representation of relations between discrete objects

In mathematics, computer science and network science, network theory is a part of graph theory. It defines networks as graphs where the nodes or edges possess attributes. Network theory analyses these networks over the symmetric relations or asymmetric relations between their (discrete) components.

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

Computational phylogenetics, phylogeny inference, or phylogenetic inference focuses on computational and optimization algorithms, heuristics, and approaches involved in phylogenetic analyses. The goal is to find a phylogenetic tree representing optimal evolutionary ancestry between a set of genes, species, or taxa. Maximum likelihood, parsimony, Bayesian, and minimum evolution are typical optimality criteria used to assess how well a phylogenetic tree topology describes the sequence data. Nearest Neighbour Interchange (NNI), Subtree Prune and Regraft (SPR), and Tree Bisection and Reconnection (TBR), known as tree rearrangements, are deterministic algorithms to search for optimal or the best phylogenetic tree. The space and the landscape of searching for the optimal phylogenetic tree is known as phylogeny search space.

<span class="mw-page-title-main">Biological network inference</span>

Biological network inference is the process of making inferences and predictions about biological networks. By using these networks to analyze patterns in biological systems, such as food-webs, we can visualize the nature and strength of these interactions between species, DNA, proteins, and more.

<span class="mw-page-title-main">Closeness centrality</span>

In a connected graph, closeness centrality of a node is a measure of centrality in a network, calculated as the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph. Thus, the more central a node is, the closer it is to all other nodes.

<span class="mw-page-title-main">Biological network</span> Method of representing systems

A biological network is a method of representing systems as complex sets of binary interactions or relations between various biological entities. In general, networks or graphs are used to capture relationships between entities or objects. A typical graphing representation consists of a set of nodes connected by edges.

The clique percolation method is a popular approach for analyzing the overlapping community structure of networks. The term network community has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering and modularity maximization.

<span class="mw-page-title-main">Betweenness centrality</span> Measure of a graphs centrality, based on shortest paths

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

<span class="mw-page-title-main">Social network</span> Social structure made up of a set of social actors

A social network is a social structure made up of a set of social actors, sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for analyzing the structure of whole social entities as well as a variety of theories explaining the patterns observed in these structures. The study of these structures uses social network analysis to identify local and global patterns, locate influential entities, and examine network dynamics.

Weighted correlation network analysis, also known as weighted gene co-expression network analysis (WGCNA), is a widely used data mining method especially for studying biological networks based on pairwise correlations between variables. While it can be applied to most high-dimensional data sets, it has been most widely used in genomic applications. It allows one to define modules (clusters), intramodular hubs, and network nodes with regard to module membership, to study the relationships between co-expression modules, and to compare the network topology of different networks. WGCNA can be used as a data reduction technique, as a clustering method, as a feature selection method, as a framework for integrating complementary (genomic) data, and as a data exploratory technique. Although WGCNA incorporates traditional data exploratory techniques, its intuitive network language and analysis framework transcend any standard analysis technique. Since it uses network methodology and is well suited for integrating complementary genomic data sets, it can be interpreted as systems biologic or systems genetic data analysis method. By selecting intramodular hubs in consensus modules, WGCNA also gives rise to network based meta analysis techniques.

In graph theory and network analysis, node influence metrics are measures that rank or quantify the influence of every node within a graph. They are related to centrality indices. Applications include measuring the influence of each person in a social network, understanding the role of infrastructure nodes in transportation networks, the Internet, or urban networks, and the participation of a given node in disease dynamics.

<span class="mw-page-title-main">Gene co-expression network</span>

A gene co-expression network (GCN) is an undirected graph, where each node corresponds to a gene, and a pair of nodes is connected with an edge if there is a significant co-expression relationship between them. Having gene expression profiles of a number of genes for several samples or experimental conditions, a gene co-expression network can be constructed by looking for pairs of genes which show a similar expression pattern across samples, since the transcript levels of two co-expressed genes rise and fall together across samples. Gene co-expression networks are of biological interest since co-expressed genes are controlled by the same transcriptional regulatory program, functionally related, or members of the same pathway or protein complex.

<span class="mw-page-title-main">Multidimensional network</span> Networks with multiple kinds of relations

In network theory, multidimensional networks, a special type of multilayer network, are networks with multiple kinds of relations. Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis, economics, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance.

<span class="mw-page-title-main">Rich-club coefficient</span>

The rich-club coefficient is a metric on graphs and networks, designed to measure the extent to which well-connected nodes also connect to each other. Networks which have a relatively high rich-club coefficient are said to demonstrate the rich-club effect and will have many connections between nodes of high degree. The rich-club coefficient was first introduced in 2004 in a paper studying Internet topology.

<span class="mw-page-title-main">Louvain method</span> Clustering and community detection algorithm

The Louvain method for community detection is a method to extract non-overlapping communities from large networks created by Blondel et al. from the University of Louvain. The method is a greedy optimization method that appears to run in time where is the number of nodes in the network.

<span class="mw-page-title-main">Steve Horvath</span> German–American aging researcher, geneticist and biostatistician

Steve Horvath is a German–American aging researcher, geneticist, and biostatistician. He is a professor at the University of California, Los Angeles known for developing the Horvath aging clock, which is a highly accurate molecular biomarker of aging, and for developing weighted correlation network analysis. His work on the genomic biomarkers of aging, the aging process, and many age related diseases/conditions has earned him several research awards. Horvath is a principal investigator at the anti-aging startup Altos Labs and co-founder of nonprofit Clock Foundation.

<span class="mw-page-title-main">Signed network</span>

In a social network analysis, a positive or a negative 'friendship' can be established between two nodes in a network; this results in a signed network. As social interaction between people can be positive or negative, so can be links between the nodes.

References

  1. ↑ Wasserman, S., Faust, K., 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, New York, NY.
  2. 1 2 3 A. Barrat and M. Barthelemy and R. Pastor-Satorras and A. Vespignani (2004). "The architecture of complex weighted networks". Proceedings of the National Academy of Sciences. 101 (11): 3747–3752. arXiv: cond-mat/0311416 . Bibcode:2004PNAS..101.3747B. doi: 10.1073/pnas.0400087101 . PMC   374315 . PMID   15007165.
  3. 1 2 3 Horvath, S., 2011. Weighted Network Analysis. Applications in Genomics and Systems Biology. Springer Book. ISBN   978-1-4419-8818-8.
  4. ↑ Granovetter, M (1973). "The strength of weak ties". American Journal of Sociology. 78 (6): 1360–1380. doi:10.1086/225469. S2CID   59578641.
  5. ↑ Luczkowich, J.J.; Borgatti, S.P.; Johnson, J.C.; Everett, M.G. (2003). "Defining and measuring trophic role similarity in food webs using regular equivalence". Journal of Theoretical Biology. 220 (3): 303–321. Bibcode:2003JThBi.220..303L. CiteSeerX   10.1.1.118.3862 . doi:10.1006/jtbi.2003.3147. PMID   12468282.
  6. ↑ D. J. Watts and Steven Strogatz (June 1998). "Collective dynamics of 'small-world' networks" (PDF). Nature . 393 (6684): 440–442. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID   9623998. S2CID   4429113. Archived from the original (PDF) on 2007-02-21.
  7. ↑ Tore Opsahl and Vittoria Colizza and Pietro Panzarasa and Jose J. Ramasco (2008). "Prominence and control: The weighted rich-club effect". Physical Review Letters. 101 (16): 168702. arXiv: 0804.0417 . Bibcode:2008PhRvL.101p8702O. doi:10.1103/PhysRevLett.101.168702. PMID   18999722. S2CID   29349737. Archived from the original on 2009-11-27. Retrieved 2009-09-17.
  8. ↑ "Operationalisation of tie strength in social networks". 2009-02-06. Archived from the original on 2009-08-24. Retrieved 2009-09-17.
  9. 1 2 Zhang, Bin; Horvath, Steve (2005). "A general framework for weighted gene co-expression network analysis". Statistical Applications in Genetics and Molecular Biology. 4: Article17. doi:10.2202/1544-6115.1128. PMID   16646834. S2CID   7756201.
  10. 1 2 Langfelder, Peter; Horvath, Steve (2008). "WGCNA: an R package for weighted correlation network analysis". BMC Bioinformatics. 9: 559. doi: 10.1186/1471-2105-9-559 . PMC   2631488 . PMID   19114008. Open Access logo PLoS transparent.svg
  11. ↑ Newman, Mark E J (2001). "Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality" (PDF). Physical Review E. 64 (1): 016132. arXiv: cond-mat/0011144 . Bibcode:2001PhRvE..64a6132N. doi:10.1103/PhysRevE.64.016132. PMID   11461356. S2CID   12985167. Archived (PDF) from the original on 2008-10-10. Retrieved 2009-09-17.
  12. ↑ Brandes, U (2008). "On variants of shortest-path betweenness centrality and their generic computation". Social Networks. 30 (2): 136–145. CiteSeerX   10.1.1.72.9610 . doi:10.1016/j.socnet.2007.11.001.
  13. ↑ Opsahl, T; Agneessens, F; Skvoretz, J (2010). "Node centrality in weighted networks: Generalizing degree and shortest paths". Social Networks. 32 (3): 245–251. doi:10.1016/j.socnet.2010.03.006. Archived from the original on 24 June 2021. Retrieved 17 June 2021.
  14. ↑ Tore Opsahl; Pietro Panzarasa (2009). "Clustering in Weighted Networks". Social Networks. 31 (2): 155–163. CiteSeerX   10.1.1.180.9968 . doi:10.1016/j.socnet.2009.02.002. S2CID   8822670. Archived from the original on 2019-07-01. Retrieved 2009-09-17.
  15. ↑ Dong J, Horvath S (2007) "Understanding Network Concepts in Modules". BMC Systems Biology 2007, June 1:24 Open Access logo PLoS transparent.svg
  16. ↑ Dong, Jun; Horvath, Steve (2008). Miyano, Satoru (ed.). "Geometric interpretation of gene coexpression network analysis". PLOS Computational Biology. 4 (8): e1000117. Bibcode:2008PLSCB...4E0117H. doi: 10.1371/journal.pcbi.1000117 . PMC   2446438 . PMID   18704157. Open Access logo PLoS transparent.svg
  17. ↑ Gursoy, Furkan; Badur, Bertan (2021-09-18). "Extracting the signed backbone of intrinsically dense weighted networks". Journal of Complex Networks. 9 (5). doi:10.1093/comnet/cnab019. ISSN   2051-1310.
  18. ↑ "tnet » Software". Tore Opsahl. 12 June 2011. Archived from the original on 15 June 2021. Retrieved 17 June 2021.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.