Network science
The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famous Seven Bridges of Königsberg written by Leonhard Euler in 1736, eulers mathematical description of vertices and edges was the foundation of graph theory, a branch of mathematics that studies the properties of pairwise relations in a network structure. The field of graph theory continued to develop and found applications in chemistry, in the 1930s Jacob Moreno, a psychologist in the Gestalt tradition, arrived in the United States. He developed the sociogram and presented it to the public in April 1933 at a convention of medical scholars, Moreno claimed that before the advent of sociometry no one knew what the interpersonal structure of a group precisely looked like. The sociogram was a representation of the structure of a group of elementary school students. The boys were friends of boys and the girls were friends of girls with the exception of one boy who said he liked a single girl and this network representation of social structure was found so intriguing that it was printed in The New York Times.
The sociogram has found many applications and has grown into the field of network analysis. Probabilistic theory in network science developed as an offshoot of graph theory with Paul Erdős, for social networks the exponential random graph model or p* is a notational framework used to represent the probability space of a tie occurring in a social network. In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model and they suggest that all organizations are structured along these three domains, Individuals and Resources. Their paper introduced the concept that networks occur across multiple domains and this field has grown into another sub-discipline of network science called dynamic network analysis. More recently other network science efforts have focused on mathematically describing different network topologies, duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Although many networks, such as the internet, appear to maintain this aspect, the U. S. military first became interested in network-centric warfare as an operational concept based on network science in 1996.
As a result, the BAST issued the NRC study in 2005 titled Network Science that defined a new field of research in Network Science for the Army. Under the tutelage of Dr. Moxley and the faculty of the USMA, in order to better instill the tenets of network science among its cadre of future leaders, the USMA has instituted a five-course undergraduate minor in Network Science. In 2006, the U. S. S. and UK, the goal of the alliance is to perform basic research in support of Network- Centric Operations across the needs of both nations. Often, networks have certain attributes that can be calculated to analyze the properties & characteristics of the network and these network properties often define network models and can be used to analyze how certain models contrast to each other. Many of the definitions for terms used in network science can be found in Glossary of graph theory. The density D of a network is defined as a ratio of the number of edges E to the number of edges, given by the binomial coefficient
Semantic network
A semantic network, or frame network, is a network that represents semantic relations between concepts. This is often used as a form of knowledge representation and it is a directed or undirected graph consisting of vertices, which represent concepts, and edges, which represent semantic relations between concepts. Typical standardized semantic networks are expressed as semantic triples, Semantic Nets were first invented for computers by Richard H. Richens of the Cambridge Language Research Unit in 1956 as an interlingua for machine translation of natural languages. It featured prominently in the work of Allan M, in the subsequent decades, the distinction between semantic networks and knowledge graphs was blurred. In 2012, Google gave their knowledge graph the name Knowledge Graph, a semantic network is used when one has knowledge that is best understood as a set of concepts that are related to one another. Most semantic networks are cognitively based and they consist of arcs and nodes which can be organized into a taxonomic hierarchy.
Semantic networks contributed ideas of spreading activation and nodes as proto-objects and you would use the assoc function with a key of canary to extract all the information about the canary type. An example of a network is WordNet, a lexical database of English. It groups English words into sets of synonyms called synsets, provides short, general definitions, some of the most common semantic relations defined are meronymy, hyponymy, hypernymy and antonymy. WordNet properties have been studied from a network theory perspective and compared to other semantic networks created from Rogets Thesaurus, from this perspective the three of them are a small world structure. It is possible to represent logical descriptions using semantic networks such as the graphs of Charles Sanders Peirce or the related conceptual graphs of John F. Sowa. These have expressive power equal to or exceeding standard first-order predicate logic, unlike WordNet or other lexical or browsing networks, semantic networks using these representations can be used for reliable automated logical deduction.
Some automated reasoners exploit the features of the networks during processing. Other examples of networks are Gellish models. Gellish English with its Gellish English dictionary, is a language that is defined as a network of relations between concepts and names of concepts. Gellish English is a subset of natural English, just as Gellish Dutch is a formal subset of Dutch. Other Gellish networks consist of models and information models that are expressed in the Gellish language. A Gellish network is a network of relations between things, each relation in the network is an expression of a fact that is classified by a relation type
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a v is denoted deg or deg v. The maximum degree of a graph G, denoted by Δ, in the graph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, the degree sum formula states that, given a graph G =, ∑ v ∈ V deg =2 | E |. The formula implies that in any graph, the number of vertices with odd degree is even and this statement is known as the handshaking lemma. The latter name comes from a mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even. The degree sequence of a graph is the non-increasing sequence of its vertex degrees. The degree sequence is a graph invariant so isomorphic graphs have the degree sequence. However, the sequence does not, in general, uniquely identify a graph, in some cases.
The degree sequence problem is the problem of finding some or all graphs with the sequence being a given non-increasing sequence of positive integers. A sequence which is the sequence of some graph, i. e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the sum formula, any sequence with an odd sum, such as. The converse is true, if a sequence has an even sum. The construction of such a graph is straightforward, connect vertices with odd degrees in pairs by a matching, the question of whether a given degree sequence can be realized by a simple graph is more challenging. This problem is called graph realization problem and can either be solved by the Erdős–Gallai theorem or the Havel–Hakimi algorithm, the problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration. A vertex with degree 0 is called an isolated vertex, a vertex with degree 1 is called a leaf vertex or end vertex, and the edge incident with that vertex is called a pendant edge.
In the graph on the right, is a pendant edge and this terminology is common in the study of trees in graph theory and especially trees as data structures. A vertex with degree n −1 in a graph on n vertices is called a dominating vertex, if each vertex of the graph has the same degree k the graph is called a k-regular graph and the graph itself is said to have degree k
Neighbourhood (graph theory)
For other meanings of neighbourhoods in mathematics, see Neighbourhood. In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge, the neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v. For example, the shows a graph of 6 vertices and 7 edges. Vertex 5 is adjacent to vertices 1,2, and 4, the neighbourhood of vertex 5 is the graph with three vertices,1,2, and 4, and one edge connecting vertices 1 and 2. The neighbourhood is often denoted NG or N, the same neighbourhood notation may be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. When stated without any qualification, a neighbourhood is assumed to be open, neighbourhoods may be used to represent graphs in computer algorithms, via the adjacency list and adjacency matrix representations. Neighbourhoods are used in the coefficient of a graph. In addition, many important classes of graphs may be defined by properties of their neighbourhoods, an isolated vertex has no adjacent vertices.
The degree of a vertex is equal to the number of adjacent vertices, a special case is a loop that connects a vertex to itself, if such an edge exists, the vertex belongs to its own neighbourhood. For instance, in the graph shown in the figure, each vertex has a neighbourhood isomorphic to a cycle of four vertices. For example, Any complete graph Kn is locally Kn-1, the only graphs that are locally complete are disjoint unions of complete graphs. A Turán graph T is locally T, more generally any Turán graph is locally Turán. Every planar graph is locally outerplanar, not every locally outerplanar graph is planar. A graph is triangle-free if and only if it is locally independent, every k-chromatic graph is locally -chromatic. Every locally k-chromatic graph has chromatic number O, if a graph family F is closed under the operation of taking induced subgraphs, every graph in F is locally F. For instance, every graph is locally chordal, every perfect graph is locally perfect. A graph is cyclic if every neighbourhood is a cycle.
For instance, the octahedron is the unique locally C4 graph, the icosahedron is the unique locally C5 graph, locally cyclic graphs can have as many as n 2 − o edges
Social network
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 local and global patterns, locate influential entities. Social networks and the analysis of them is an inherently interdisciplinary academic field which emerged from social psychology, statistics, georg Simmel authored early structural theories in sociology emphasizing the dynamics of triads and web of group affiliations. Jacob Moreno is credited with developing the first sociograms in the 1930s to study interpersonal relationships and these approaches were mathematically formalized in the 1950s and theories and methods of social networks became pervasive in the social and behavioral sciences by the 1980s.
Social network analysis is now one of the major paradigms in contemporary sociology, together with other complex networks, it forms part of the nascent field of network science. The social network is a theoretical construct useful in the sciences to study relationships between individuals, organizations, or even entire societies. The term is used to describe a structure determined by such interactions. The ties through which any given social unit connects represent the convergence of the social contacts of that unit. This theoretical approach is, relational, one common criticism of social network theory is that individual agency is often ignored although this may not be the case in practice. Precisely because many different types of relations, singular or in combination, form these network configurations, in the late 1890s, both Émile Durkheim and Ferdinand Tönnies foreshadowed the idea of social networks in their theories and research of social groups. Tönnies argued that groups can exist as personal and direct social ties that either link individuals who share values and belief or impersonal, formal.
Major developments in the field can be seen in the 1930s by several groups in psychology, anthropology, in psychology, in the 1930s, Jacob L. Moreno began systematic recording and analysis of social interaction in small groups, especially classrooms and work groups. In anthropology, the foundation for social theory is the theoretical and ethnographic work of Bronislaw Malinowski, Alfred Radcliffe-Brown. In sociology, the work of Talcott Parsons set the stage for taking a relational approach to understanding social structure. Later, drawing upon Parsons theory, the work of sociologist Peter Blau provides a strong impetus for analyzing the relational ties of social units with his work on social exchange theory, by the 1970s, a growing number of scholars worked to combine the different tracks and traditions. In general, social networks are self-organizing and complex and these patterns become more apparent as network size increases. However, a network analysis of, for example, all interpersonal relationships in the world is not feasible and is likely to contain so much information as to be uninformative
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph, in the special case of a finite simple graph, the adjacency matrix is a -matrix with zeros on its diagonal. If the graph is undirected, the matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its matrix is studied in spectral graph theory. The adjacency matrix should be distinguished from the matrix for a graph. The diagonal elements of the matrix are all zero, since edges from a vertex to itself are not allowed in simple graphs and it is sometimes useful in algebraic graph theory to replace the nonzero elements with algebraic variables. Loops may be counted either once or twice, as long as a consistent convention is followed, undirected graphs often use the latter convention of counting loops twice, whereas directed graphs typically use the former convention.
In this case, the smaller matrix B uniquely represents the graph, B is sometimes called the biadjacency matrix. Formally, let G = be a graph with parts U = and V =. The biadjacency matrix is the r × s 0–1 matrix B in which bi, j =1 if and only if ∈ E. If G is a multigraph or weighted graph the elements bi. An -adjacency matrix A of a graph has Ai, j = a if is an edge, b if it is not. The Seidel adjacency matrix is a -adjacency matrix and this matrix is used in studying strongly regular graphs and two-graphs. The distance matrix has in position the distance between vertices vi and vj, the distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, the convention followed here is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2. This allows the degree of a vertex to be found by taking the sum of the values in either its respective row or column in the adjacency matrix.
In directed graphs, the in-degree of a vertex can be computed by summing the entries of the row
Dependency network
The dependency network approach provides a system level analysis of the activity and topology of directed networks. The approach extracts causal topological relations between the nodes, and provides an important step towards inference of causal activity relations between the network nodes. This methodology has originally been introduced for the study of data, it has been extended and applied to other systems, such as the immune system. In the case of network activity, the analysis is based on partial correlations, in simple words, the partial correlation is a measure of the effect of a given node, say j, on the correlations between another pair of nodes, say i and k. Using this concept, the dependency of one node on another node, is calculated for the entire network and this results in a directed weighted adjacency matrix, of a fully connected network. The partial correlation based Dependency Networks is a new class of correlation based networks. This original methodology was first presented at the end of 2010 and this research, headed by Dror Y.
Kenett and his Ph. D. supervisor Prof. Eshel Ben-Jacob, collaborated with Dr. Michele Tumminello and they quantitatively uncovered hidden information about the underlying structure of the U. S. stock market, information that was not present in the standard correlation networks. Thus, they were able for the first time to show the dependency relationships between the different economic sectors. Following this work, the dependency network methodology has been applied to the study of the immune system, as such, this methodology is applicable to any complex system. To be more specific, the correlations of the pair. Defined this way, the difference between the correlations and the partial correlations provides a measure of the influence of node j on the correlation. Therefore, we define the influence of node j on node i, or the dependency of node i on node j- D, in the case of network topology, the analysis is based on the effect of node deletion on the shortest paths between the network nodes. Note that the correlations for all pairs of nodes define a symmetric correlation matrix whose element is the correlation between nodes i and j.
Next we use the resulting node correlations to compute the partial correlations, the first order partial correlation coefficient is a statistical measure indicating how a third variable affects the correlation between two other variables. The partial correlation between nodes i and k with respect to a third node j − P C is defined as, P C = C − C C where C, C and C are the node correlations defined above. We note that this quantity can be viewed either as the dependency of C on node j. The node activity dependencies define a dependency matrix D whose element is the dependency of node i on node j, for this reason, some of the methods used in the analyses of the correlation matrix have to be replaced or are less efficient
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements called nodes or vertices, therefore, E is a subset of P ∖, where P is the power set of X. While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, however, it is often desirable to study hypergraphs where all hyperedges have the same cardinality, a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, a hypergraph is called a set system or a family of sets drawn from the universal set X. The difference between a set system and a hypergraph is in the questions being asked, there are variant definitions, sometimes edges must not be empty, and sometimes multiple edges, with the same set of nodes, are allowed. Hypergraphs can be viewed as incidence structures, in computational geometry, a hypergraph may sometimes be called a range space and the hyperedges are called ranges.
In cooperative game theory, hypergraphs are called simple games, this notion is applied to problems in social choice theory. In some literature edges are referred to as hyperlinks or connectors, the collection of hypergraphs is a category with hypergraph homomorphisms as morphisms. Because hypergraph links can have any cardinality, there are notions of the concept of a subgraph, called subhypergraphs, partial hypergraphs. Let H = be the hypergraph consisting of vertices X =, and having edge set E =, a subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph H A induced by a subset A of X is defined as H A =, the partial hypergraph is a hypergraph with some edges removed. Given a subset J ⊂ I e of the index set. Given a subset A ⊆ X, the hypergraph is the partial hypergraph H × A =. The dual H ∗ of H is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by and whose edges are given by where X m =. When a notion of equality is properly defined, as done below, a connected graph G with the same vertex set as a connected hypergraph H is a host graph for H if every hyperedge of H induces a connected subgraph in G.
For a disconnected hypergraph H, G is a host graph if there is a bijection between the components of G and of H, such that each connected component G of G is a host of the corresponding H. The 2-section of a hypergraph is the graph with the vertices of the hypergraph. This bipartite graph is called incidence graph, a first definition of acyclicity for hypergraphs was given by Claude Berge, a hypergraph is Berge-acyclic if its incidence graph is acyclic
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a graph in which every pair of distinct vertices is connected by a pair of unique edges. Graph theory itself is dated as beginning with Leonhard Eulers 1736 work on the Seven Bridges of Königsberg. However, drawings of graphs, with their vertices placed on the points of a regular polygon, appeared already in the 13th century. Such a drawing is referred to as a mystic rose. The complete graph on n vertices is denoted by Kn, Kn has n/2 edges, and is a regular graph of degree n −1. All complete graphs are their own maximal cliques and they are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. The complement graph of a graph is an empty graph. If the edges of a graph are each given an orientation. The number of matchings of the graphs are given by the telephone numbers 1,1,2,4,10,26,76,232,764,2620,9496,35696,140152,568504,2390480,10349536,46206736.
These numbers give the largest possible value of the Hosoya index for an n-vertex graph, the number of perfect matchings of the complete graph Kn is given by the double factorial. The crossing numbers up to K27 are known, with K28 requiring either 7233 or 7234 crossings, further values are collected by the Rectilinear Crossing Number project. Crossing numbers for Kn are 0,0,0,0,1,3,9,19,36,62,102,153,229,324,447,603,798,1029,1318,1657,2055,2528,3077,3699,4430,5250,6180. A complete graph with n nodes represents the edges of an -simplex, geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. The Császár polyhedron, a polyhedron with the topology of a torus, has the complete graph K7 as its skeleton. Every neighborly polytope in four or more dimensions has a complete skeleton, k1 through K4 are all planar graphs. As part of the Petersen family, K6 plays a role as one of the forbidden minors for linkless embedding. In other words, and as Conway and Gordon proved, every embedding of K6 into three-dimensional space is intrinsically linked and Gordon showed that any three-dimensional embedding of K7 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph, equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. One often writes G = to denote a graph whose partition has the parts U and V. If | U | = | V |, that is, if all vertices on the same side of the bipartition have the same degree, G is called biregular. When modelling relations between two different classes of objects, bipartite graphs very often arise naturally, a third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design, the charts numismatists produce to represent the production of coins are bipartite graphs. More abstract examples include the following, Every tree is bipartite, cycle graphs with an even number of vertices are bipartite. Every planar graph whose faces all have even length is bipartite, special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
It follows that Km, n has mn edges, closely related to the complete bipartite graphs are the crown graphs, formed from complete bipartite graphs by removing the edges of a perfect matching. Hypercube graphs, partial cubes, and median graphs are bipartite, in these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have a number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of graphs, and every median graph is a partial cube. Bipartite graphs may be characterized in different ways, A graph is bipartite if. A graph is bipartite if and only if it is 2-colorable, the spectrum of a graph is symmetric if and only if its a bipartite graph. In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching, an alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
In any graph without isolated vertices the size of the edge cover plus the size of a maximum matching equals the number of vertices. Perfection of bipartite graphs is easy to see but perfection of the complements of bipartite graphs is less trivial and this was one of the results that motivated the initial definition of perfect graphs. The bipartite graphs, line graphs of graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem
Evolving networks
Evolving Networks are networks that change as a function of time. They are an extension of network science since almost all real world networks evolve over time. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields. The study of networks traces its foundations to the development of graph theory, probabilistic network theory developed with the help of eight famous papers studying random graphs written by Paul Erdős and Alfréd Rényi. The Erdős-Rényi model supposes that a graph is composed of N labeled nodes where each pair of nodes is connected by a probability p. While the ER models simplicity has helped it find many applications, the ER model fails to generate local clustering and triadic closures as often as they are found in real world networks. Therefore, the Watts and Strogatz model was proposed, whereby a network is constructed as a ring lattice. This produces a locally clustered network and dramatically reduces the path length.
Despite this achievement, both the ER and the Watts and Storgatz models fail to account for the formulation of hubs as observed in real world networks. The degree distribution in the ER model follows a Poisson distribution, while the Watts and this was accomplished by incorporating preferential attachment and growth, where nodes are added to the network over time and are more likely to link to other nodes with high degree distributions. The BA model was first applied to distributions on the web. New web pages are added over time, and each new page is likely to link to highly visible hubs like Google which have high degree distributions than to nodes with only a few links. However, the model only the simplest assumptions necessary for a scale-free network to emerge, namely that there is linear growth. This minimal model does not capture variations in the shape of the distribution, variations in the degree exponent. Therefore, the model has since been modified to more fully capture the properties of evolving networks by introducing a few new properties.
However, this can be alleviated by introducing a fitness for each node, Π = η i k i ∑ j η j k j, Where η is the fitness, which may depend on time. Additionally, existing links may be destroyed and new links between existing nodes may be created, the probability of these actions occurring may depend on time and may be related to the nodes fitness. Probabilities can be assigned to these events by studying the characteristics of the network in question in order to grow a network with identical properties