47 Network theory

Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes.

Assortativity, or assortative mixing is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree. The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

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.

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various potential new states; unlike in a pure random walk, the probabilities of the potential new states are unequal.

Bose–Einstein condensation (network theory)

Bose–Einstein condensation in networks is a phase transition observed in complex networks that can be described by the Bianconi–Barabási model. This phase transition predicts a "winner-takes-all" phenomena in complex networks and can be mathematically mapped to the mathematical model explaining Bose–Einstein condensation in physics.

In graph theory and network analysis, indicators of centrality identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin. They should not be confused with node influence metrics, which seek to quantify the influence of every node in the network.

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.

Core periphery structure is a network theory model based on Immanuel Wallerstein's world-systems theory. He formulated the chart in the 1980s.

The critical path method (CPM), or critical path analysis (CPA), is an algorithm for scheduling a set of project activities. It is commonly used in conjunction with the program evaluation and review technique (PERT). A critical path is determined by identifying the longest stretch of dependent activities and measuring the time required to complete them from start to finish.

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

Degree Preserving Randomization is a technique used in Network Science that aims to assess whether or not variations observed in a given graph could simply be an artifact of the graph's inherent structural properties rather than properties unique to the nodes, in an observed network.

A scale-free network is a type of networks that is of particular interest of network science. It is characterized by its degree distribution following a power law. While the most widely known generative models for scale-free networks are stochastic, such as the Barabási–Albert model or the Fitness model can reproduce many properties of real-life networks by assuming preferential attachment and incremental growth, the understanding of deterministic scale-free networks leads to valuable, analytical results.

Distinctiveness centrality is a network centrality measure, used in graph analysis. It is similar to degree centrality, but weighted in order to attribute higher importance to distinctive, non-redundant, connections.

In network science, the efficiency of a network is a measure of how efficiently it exchanges information. The concept of efficiency can be applied to both local and global scales in a network. On a global scale, efficiency quantifies the exchange of information across the whole network where information is concurrently exchanged. The local efficiency quantifies a network's resistance to failure on a small scale. That is the local efficiency of a node characterizes how well information is exchanged by its neighbors when it is removed.

Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.

Exponential random graph models (ERGMs) are a family of statistical models for analyzing data about social and other networks. Examples of networks examined using ERGM include knowledge networks, organizational networks, colleague networks, social media networks, networks of scientific development, and others.

Fractal analysis is useful in the study of complex networks, present in both natural and artificial systems such as computer systems, brain and social networks, allowing further development of the field in network science.

Gephi is an open-source network analysis and visualization software package written in Java on the NetBeans platform.

Global cascades models are a class of models aiming to model large and rare cascades that are triggered by exogenous perturbations which are relatively small compared with the size of the system. The phenomenon occurs ubiquitously in various systems, like information cascades in social systems, stock market crashes in economic systems, and cascading failure in physics infrastructure networks. The models capture some essential properties of such phenomenon.

The global shipping network is the worldwide network of maritime traffic. From a network science perspective ports represent nodes and routes represent lines. Transportation networks have a crucial role in today's economy, more precisely, maritime traffic is one of the most important drivers of global trade.

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as the brain or the Internet.

A human disease network is a network of human disorders and diseases with reference to their genetic origins or other features. More specifically, it is the map of human disease associations referring mostly to disease genes. For example, in a human disease network, two diseases are linked if they share at least one associated gene. A typical human disease network usually derives from bipartite networks which consist of both diseases and genes information. Additionally, some human disease networks use other features such as symptoms and proteins to associate diseases.

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into a hyperbolic space of constant negative curvature and (2) an edge between two nodes is present if they are close according to a function of the metric. A HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

The Louvain method for community detection is a method to extract 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 if is the number of nodes in the network.

In the scale-free network theory, a mediation-driven attachment (MDA) model appears to embody a preferential attachment rule tacitly rather than explicitly. According to MDA rule, a new node first picks a node from the existing network at random and connect itself not with that but with one of the neighbors also picked at random.

Modularity is one measure of the structure of networks or graphs. It was designed to measure the strength of division of a network into modules. Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. However, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities. Biological networks, including animal brains, exhibit a high degree of modularity.

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, infrastructures and finance.

Network Controllability is concerned about the structural controllability of a network. Controllability describes our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al. on multi-type biological networks identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.

A network on a chip or network-on-chip is a network-based communications subsystem on an integrated circuit ("microchip"), most typically between modules in a system on a chip (SoC). The modules on the IC are typically semiconductor IP cores schematizing various functions of the computer system, and are designed to be modular in the sense of network science. The network on chip is a router-based packet switching network between SoC modules.

A network scheduler, also called packet scheduler, queueing discipline, qdisc or queueing algorithm, is an arbiter on a node in packet switching communication network. It manages the sequence of network packets in the transmit and receive queues of the network interface controller. There are several network schedulers available for the different operating systems, that implement many of the existing network scheduling algorithms.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

A network is an abstract structure capturing only the basics of connection patterns and little else. Because it is a generalized pattern, tools developed for analyzing, modeling and understanding networks can theoretically be implemented across disciplines. As long as a system can be represented by a network, there is an extensive set of tools – mathematical, computational, and statistical – that are well-developed and if understood can be applied to the analysis of the system of interest.

Node deletion is the procedure of removing a node from a network, where the node is either chosen randomly or directly. Node deletion is used to test the robustness and the attack tolerance of networks. Understanding how a network changes in response to node deletion is critical in many empirical networks. Application varies across many fields, including the breakdown of the World Wide Web via router removal, elimination of epidemics or fighting against criminal organizations.

NodeXL is a network analysis and visualization software package for Microsoft Excel 2007/2010/2013/2016. The free version contains network visualization and social network analysis features. The commercial version includes access to social media network data importers, advanced network metrics, and automation. It is a popular package similar to other network visualization tools such as Pajek, UCINet, and Gephi.

A pollination network is a bipartite mutualistic network in which plants and pollinators are the nodes, and the pollination interactions form the links between these nodes. The pollination network is bipartite as interactions only exist between two distinct, non-overlapping sets of species, but not within the set: a pollinator can never be pollinated, unlike in a predator-prey network where a predator can be depredated. A pollination network is two-modal, i.e., it includes only links connecting plant and animal communities.

The program (or project) evaluation and review technique (PERT) is a statistical tool used in project management, which was designed to analyze and represent the tasks involved in completing a given project.

Being a component part of network science the study of quantum complex networks aims to explore the impact of complexity science and network architectures in quantum systems. According to quantum information theory it is possible to improve communication security and data transfer rates by taking advantage of quantum mechanics. In this context the study of quantum complex networks is motivated by the possibility of quantum communications being used on a massive scale in the future. In such case it is likely that quantum communication networks will acquire non trivial features as is common in existing communication networks today.

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.

Semantic Brand Score

The Semantic Brand Score is a measure designed to assess the importance of one or more brands, in different contexts and whenever textual data is available. This metric has its foundations in graph theory and combines methods of text mining and social network analysis. The Semantic Brand Score was developed based on the conceptualizations of brand equity proposed by Keller and Aaker. These well-known models inspired the measurement of a different construct on textual data: brand importance.

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Similarity in network analysis occurs when two nodes fall in the same equivalence class.

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.

The structural cut-off is a concept in network science which imposes a degree cut-off in the degree distribution of a finite size network due to structural limitations. Networks with vertices with degree higher than the structural cut-off will display structural disassortativity.

A temporal network, also known as a time-varying network, is a network whose links are active only at certain points in time. Each link carries information on when it is active, along with other possible characteristics such as a weight. Time-varying networks are of particular relevance to spreading processes, like the spread of information and disease, since each link is a contact opportunity and the time ordering of contacts is included.

The term tribe or digital tribe is used as a slang term for an unofficial community or organization of people who share a common interest, and usually who are loosely affiliated with each other through social media or other Internet mechanisms. The term is related to "tribe", which traditionally refers to people closely associated in both geography and genealogy. Nowadays, it looks more like a virtual community or a personal network and it is often called global digital tribe. Most anthropologists agree that a tribe is a (small) society that practices its own customs and culture, and that these define the tribe. The tribes are divided into clans, with their own customs and cultural values that differentiate them from activities that occur in 'real life' contexts. People feel more inclined to share and defend their ideas on social networks than they would dare to say to someone face to face. For example, it would be ridiculous to 'poke' someone in real life.

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. The elements of a system are represented as nodes 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.

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the bottleneck shortest path problem or the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.