|
Girvan–Newman Algorithm
The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.Girvan M. and Newman M. E. J.Community structure in social and biological networks Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002) Edge betweenness and community structure The Girvan–Newman algorithm detects communities by progressively removing edges from the original network. The connected components of the remaining network are the communities. Instead of trying to construct a measure that tells us which edges are the most central to communities, the Girvan–Newman algorithm focuses on edges that are most likely "between" communities. Vertex betweenness is an indicator of highly central nodes in networks. For any node i, vertex betweenness is defined as the fraction of shortest paths between pairs of nodes that run through it. It is relevant to models where the network modulates transfer of goods between known start and end n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Michelle Girvan
Michelle Girvan (born 1977) is an American physicist and network scientist whose research combines methods from dynamical systems, graph theory, and statistical mechanics and applies them to problems including epidemiology, gene regulation, and the study of Information cascades. She is one of the namesakes of the Girvan–Newman algorithm, used to detect community structure in complex systems. Girvan is a professor of physics at the University of Maryland, College Park. Education and career Girvan graduated from the Massachusetts Institute of Technology in 1999, with a double major in mathematics and physics and a minor in political science. She completed a Ph.D. in physics at Cornell University in 2004. Her dissertation, ''The Structure and Dynamics of Complex Networks'', was supervised by Steven Strogatz. After postdoctoral research at the Santa Fe Institute The Santa Fe Institute (SFI) is an independent, nonprofit theoretical research institute located in Santa Fe, New ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mark Newman
Mark Newman is an English-American physicist and Anatol Rapoport Distinguished University Professor of Physics at the University of Michigan, as well as an external faculty member of the Santa Fe Institute. He is known for his fundamental contributions to the fields of complex networks and complex systems, for which he was awarded the 2014 Lagrange Prize. Career Mark Newman grew up in Bristol, England, where he was a pupil at Bristol Cathedral School, and earned both an undergraduate degree and a PhD in physics from the University of Oxford, before moving to the United States to conduct research first at Cornell University and later at the Santa Fe Institute, a private research institute in northern New Mexico devoted to the study of complex systems. In 2002 Newman moved to the University of Michigan, where he is currently the Anatol Rapoport Distinguished University Professor of Physics and a professor in the university's Center for the Study of Complex Systems. Research ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Community Structure
In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally. In the particular case of ''non-overlapping'' community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But ''overlapping'' communities are also allowed. The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. A related but different problem is community search, where the goal is to find a community that a certain vertex belongs to. Properties In the study of networks, such as computer and information networks, social networks and biological networks, a number of different charac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complex System
A complex system is a system composed of many components which may interact with each other. Examples of complex systems are Earth's global climate, organisms, the human brain, infrastructure such as power grid, transportation or communication systems, complex software and electronic systems, social and economic organizations (like cities), an ecosystem, a living cell, and ultimately the entire universe. Complex systems are systems whose behavior is intrinsically difficult to model due to the dependencies, competitions, relationships, or other types of interactions between their parts or between a given system and its environment. Systems that are " complex" have distinct properties that arise from these relationships, such as nonlinearity, emergence, spontaneous order, adaptation, and feedback loops, among others. Because such systems appear in a wide variety of fields, the commonalities among them have become the topic of their independent area of research. In many cases, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Betweenness Centrality
In graph theory, betweenness centrality (or "betweeness 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 (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex. Betweenness centrality was devised as a general measure of centrality: it applies to a wide range of problems in network theory, including problems related to social networks, biology, transport and scientific cooperation. Although earlier authors have intuitively described centrality as based on betweenness, gave the first formal definition of betweenness centrality. Betweenness centrality finds wide application in network theory; it represents the degree to which nod ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Centrality
In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press. Definition and characterization of centrality indices Centrality indices are answers to the question "What characterizes an important vertex?" The answer is given in terms of a real-valued function on the vertices of a graph, where the values produced are expected to provide a ranking which identifies the most important nodes. The word "importance" has a wide number of meanings, leading to many di ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dendrogram
A dendrogram is a diagram representing a tree. This diagrammatic representation is frequently used in different contexts: * in hierarchical clustering, it illustrates the arrangement of the clusters produced by the corresponding analyses. * in computational biology, it shows the clustering of genes or samples, sometimes in the margins of heatmaps. * in phylogenetics, it displays the evolutionary relationships among various biological taxa. In this case, the dendrogram is also called a phylogenetic tree. The name ''dendrogram'' derives from the two ancient greek words (), meaning "tree", and (), meaning "drawing, mathematical figure". Clustering example For a clustering example, suppose that five taxa (a to e) have been clustered by UPGMA based on a matrix of genetic distances. The hierarchical clustering dendrogram would show a column of five nodes representing the initial data (here individual taxa), and the remaining nodes represent the clusters to which the d ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Closeness (mathematics)
Closeness is a basic concept in topology and related areas in mathematics. Intuitively we say two sets are close if they are arbitrarily near to each other. The concept can be defined naturally in a metric space where a notion of distance between elements of the space is defined, but it can be generalized to topological spaces where we have no concrete way to measure distances. The closure operator ''closes'' a given set by mapping it to a closed set which contains the original set and all points close to it. The concept of closeness is related to limit point. Definition Given a metric space (X,d) a point p is called close or near to a set A if :d(p,A) = 0, where the distance between a point and a set is defined as :d(p, A) := \inf_ d(p, a). Similarly a set B is called close to a set A if :d(B,A) = 0 where :d(B, A) := \inf_ d(b, A). Properties *if a point p is close to a set A and a set B then A and B are close (the converse is not true!). *closeness between a point and a s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hierarchical Clustering
In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories: * Agglomerative: This is a " bottom-up" approach: Each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. * Divisive: This is a "top-down" approach: All observations start in one cluster, and splits are performed recursively as one moves down the hierarchy. In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram. The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of \mathcal(n^3) and requires \Omega(n^2) memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modularity (networks)
Modularity is a measure of the structure of networks or graphs which measures the strength of division of a network into modules (also called groups, clusters or communities). 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. Motivation Many scientifically important problems can be represented and empirically studied using networks. For example, biological and social patterns, the World Wide Web, metabolic networks, food webs, neural networks and pathological networks are real world problems that can be mathematically represented and topologically studied to reveal some unexpected str ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Algorithms
The following is a list of well-known algorithms along with one-line descriptions for each. Automated planning Combinatorial algorithms General combinatorial algorithms * Brent's algorithm: finds a cycle in function value iterations using only two iterators * Floyd's cycle-finding algorithm: finds a cycle in function value iterations * Gale–Shapley algorithm: solves the stable marriage problem * Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ** ACORN generator ** Blum Blum Shub ** Lagged Fibonacci generator ** Linear congruential generator ** Mersenne Twister Graph algorithms * Coloring algorithm: Graph coloring algorithm. * Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching * Hungarian algorithm: algorithm for finding a perfect matching * Prüfer coding: conversion between a labeled tree an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Networks
Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics * Networks, a graph with attributes studied in network theory ** Scale-free network, a network whose degree distribution follows a power law ** Small-world network, a mathematical graph in which most nodes are not neighbors, but have neighbors in common * Flow network, a directed graph where each edge has a capacity and each edge receives a flow Biology * Biological network, any network that applies to biological systems * Ecological network, a representation of interacting species in an ecosystem * Neural network, a network or circuit of neurons Technology and communication * Artificial neural network, a computing system inspired by animal brains * Broadcast network, radio stations, television stations, or other electronic media outl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
