Network properties
This is a work in progress. It is an attempt to catalog the properties of nodes, links and networks. Contributions are welcome, please email to jdav2002-at-earthlink.net. See also my Networks and dialectics blog.
To do:
Missing references?
Add explanation of how properties are measured or quantified
Review network form levels of practice -- extrapolate from that general network properties?
Node properties
- function: what the node does (a node may have several)
- link count: the number of links a node has
- connectivity: another way of thinking about link count, though maybe the quality of the links should also be taken into account. Of Malcolm Gladwell's (2001) three key social types necessary for social phenonmena to "tip", nodes with a high link count or high connectivity would be "connectors".
- resource depth: the depth of "knowledge" or "information" or resources in the node, the resource well. Of Gladwell's (2001) tipping personality types, these would be the "mavens", the experts others go to for advice on the best whatever.
Although this is concept is raised in a social context, it could apply to other types of nodes. For example, wikipedia.org is a node rich in accumulated encyclopedic-type knowledge (as opposed to a Google that is rich in connections).
- persuasiveness: the ability of the node to affect, or change, other nodes. Gladwell's (2001) "salesmen" (sic).
- attachment cost: the cost of attaching to the node -- how "expensive" is it to add an additional connection to the node?
- fitness: the ability of a node to attract or gain new links. Fitness may change over time. Fitness may be due to many things (connectedness, resource depth, "hipness", potential, etc.)
- intelligence: refers to the knowledge a node has of links in the network, and routes to other nodes. This would affect things like search strategies in the network (after Watts, 2003). This is a more specific kind of knowledge than that described above in "resource depth", in that it refers knowledge or intelligence about the network.
- power: the ability of the node to control other nodes. The idea here is that power is distributed unevenly in some networks (especially in social networks, e.g., capitalists and workers, or men and women, or white and black, etc.)
- change threshold: the point at which a node changes. Change threshold and connectivity together determine the possibility of global cascades in the network
- processing speed or turnaround time or relay time: the length of time a node holds on to a packet before responding or forwarding it along
- security: the ability of the node to carry out its functions
- location: Location in the network is a function of "between-ness" ("measures the control a node has over what flows in the network - how often is this node on the path between other nodes?") and "closeness" ("Closeness measures how easily a node can access what is available via the network - how quickly can this node reach all others in the network?"). Location affects the power of a node. (Krebs, 2004)
Link properties
- direction: the direction of flow of whatever across the link -- from, to, or from and to; or, a -> b, a <- b, or a <-> b
- speed: the time to get from one node to another.
- bandwidth: the volume or amount that can be transferred between nodes in a given unit of time
- frequency: how often the link is utilized. This is related to speed.
- protocol: the rules that govern how nodes connect
- strength: Granovetter's concept of weak links and strong ties. This may be an aggregate way of thinking about bandwidth, speed, frequency and protocol. Or a factor of the degree of mutual dependency of nodes. Or the frequency of interaction. In social terms, "strong ties" are between close friends, weak links are between acquaintances.
- durability/longevity: links may decay over time. The opposite effect may happen also (strengthen over time).
- reliability: the likelihood that the content will arrive at the destination node complete and intact
- security
Network properties
- architectural class: "centralized" ("one central hub where everything must pass and be authorized, as in the old telephone switching systems"); "decentralized" ("more than one center, but these subcenters still being authorative such as the
airport system in the U.S. centered around hubs where planes must pass through"); or "distributed" ("bubs may exist, but are not obligatory (such as the internet). In distributed networks, participants may freely link with each other, they are fully autonomous agents.") (Bauwens, 2005, referring to Alex Galloway's Protocol).
The difference between this property and link distribution has to do with a power dimension -- how concentrated or dispersed "power" or "control" across nodes.
- selected-ness: true if the network developed or evolved under "selective pressure" (e.g., as in "natural selection", where some features would tend to persist because of environmental or other pressures) (Changizi and He, 2005)
- behavioral-ness: true if the network demonstrates "network-level behaviors". (Changizi and He, 2005)
- size: number of nodes.
- diameter: maximum number of nodes to be crossed to get from any one node to any other node
- speed: the speed with which a network process information. The speed of the network depends on the speed of nodes and links. If the network is conceived of as an information processor, the speed of a network can also be thought of as the length of the decision-making cycle.
- degree of clustering: clusters are groups of nodes that are tightly linked together, but not necessarily to nodes outside of their cluster.
- link distribution or
- scale: Scale describes how links are distributed among nodes. In a random network, nodes are distributed according to a normal, bell-curve distribution (or maybe a Poisson distribution? not sure in practice what the difference is).
"A random network has a characteristic scale in its node connectivity, embodied by the average node and fixed by the peak of the degree distribution [the bell - jd]. In contrast, the absence of a peak in a power-law degree distribution
implies that in a real network there is no such thing as a characteristic node." (Barabasi, 70) Hence, the power-law distribution is described as "scale-free".
- distribution exponent: in a power-law curve type distribution, the distribution exponent describes the shape of the distribution curve.
- motifs: repeated structures that appear in the network, typically involving more three or four nodes -- "[M]otifs can define broad classes of networks, each with specific types of elementary structures. The motifs reflect the underlying processes that generated each type of network." (Milo et al. 2002) Or, "we imagine that these simple units, or network motifs, provide specific regulatory capacities such as positive and negative feedback loops. The frequency with which cells use individual motifs reveals the regulatory strategies that were selected during evolution." (Young Lab, n.d.)
- law system: In dialectics, phenomena occur within an environment or field of phenomena. The interconnections within the process are not haphazard, but constrained or ordered in some way. "Laws" are these "general necessary connections" between (in network terms) the nodes. Or, "a law is that which cannot fail to take place under given conditions." (Sheptulin, 1978) A "law system" is the sum the laws which describe and constrain the overall behavior of the network.
- utility: There are various observations about networks that describe their usefulness. E.g., "Sarnoff's Law" (see above); "Metcalfe's Law" ("the usefulness, or utility, of a network equals the square of the number of users", where users can be a special kind of "smart" node); and "Reed's Law" ("networks that support the construction of communicating groups create value that scales exponentially with network size"). (Rheingold, 2002)
- potential for global cascade: a global cascades is a rapid transformation of the network. The possibility of global cascade is a function of node change threshold and connectivity
Emergent properties of real-world networks
- Presence of superconnectors: If a network is growing, and the property of preferential attachment exists (that is, new nodes are free to associate with any node, but "prefer" to associate with well-connected nodes -- nodes that already have many connections), then the distribution of nodes in the network will assume a "power law" distribution -- a few nodes have many links, and many nodes have few links. There is no meaningful "average", hence these are sometimes called "scale-free" networks. This type of distribution is much different from a standard or Poisson or bell-curve type distribution. The nodes that have many links are referred to as "hubs" or "superconnectors".
- Scale-free (see superconnectors)
- Small world effect: the presence of superconnectors give a network a "small-world effect". The structure of the network combines clusters of tightly connected nodes that link to other clusters through superconnectors, meaning that the diameter of the network can be fairly small even in a network with many nodes. For example any of the 1 billion plus web pages on the Internet is reachable in about 20 clicks. (Buchanan, 2002) Amaral et al. (2000) have identified three classes of small-world networks. Besides scale-free networks ("vertex connectivity distribution that decays as a power law"), they have identified
broad-scale networks ("characterized by a connectivity distribution that has a power law regime followed by a sharp cutoff", and single-scale networks ("characterized by a connectivity distribution with a fast decaying tail") These classes emerge based on differences in attachment cost and node fitness.
- Robustness: because links are distributed disproportiontately, the failure of any single node will most likely not have a serious impact on the functioning of the network, making real-world networks "robust", and likely routine failures. However, because of the importance of superconnectors, real-world networks can be vulnerable to targeted attacks.
References
Amaral, L. A. N., A. Scala, M. Barthélémy, and H. E. Stanley. 2000. Classes of real-world networks. Proceedings of the National Academy of Sciences of North America. Vol. 97, no. 21, 11149-11152.
Bauwens, Michel. 2005. "Peer to Peer and Human Evolution." http://integralvisioning.org/article.php?story=p2ptheory1.
Changizi, Mark A. and He, Darrien. 2005. "Four Correlates of Complex Behavioral Networks: Differentiation, Behavior, Connectivity, and Compartmentalization." Complexity. Volume 10, Issue 6.
Barabasi, Albert-Laszlo. 2002. Linked: The New Science of Networks. Perseus Publishing. Cambridge, MA.
Buchanan, Mark. 2002. Nexus: Small Worlds and the Groundbreaking Science of Networks. W. W. Norton. New York.
Gladwell, Malcolm. 2000. The Tipping Point: How Little Things Can Make a Big Difference. Little, Brown and Company.
Krebs, Valdis. 2004. "Power in networks".
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., U. Alon. 2002. "Network Motifs: Simple Building Blocks of Complex Networks". Science 298, 824 (October 25, 2002).
Rheingold, Howard. 2003. Smart Mobs: The Next Social Revolution. Perseus Publishing.
Watts, Duncan. 2003. Six Degrees: The Science of a Connected Age. W.W. Norton and Co.
Young Lab. (no date). "Network motifs" from "Transcriptional Regulatory Networks in Saccharomyces cerevisiae" . Cambridge, MA.
Last updated 03/13/06