Network Theory and Social Complexity - Fall 2007

From InterSciWiki
Jump to: navigation, search

Network theory

Network Theory and Social Complexity Seminar


See: Network Theory and Social Complexity - Fall 2008 - Network Theory and Social Complexity

(Fall 2007) Soc Sci 289B (72595), Anthro 289B (60554) Tues 9-11:50, SSPA 4249. Office hours Thursday 2-3:15. Thurs 22 is Thanksgiving. Thurs 29 I am at a conference.

The (Mis)Behavior of Markets: A Fractal view of Risk, Ruin & Reward. 2004. Benoit Mandelbrot & Richard L. Hudson. Basic books. A book review from: Journal of Economic Behavior and Organization Methods and Techniques of Complex Systems Science: An Overview Authors: Cosma Rohilla Shalizi (Center for the Study of Complex Systems, University of Michigan) (Submitted on 9 Jul 2003 (v1), last revised 24 Mar 2006 (this version, v4))

For the earlier version see Network Theory and Social Complexity - Anthro Version

Participants can freely post sites to the wiki, review items in the wiki, attend local events listed, edit wiki pages, talk to other participants, post CVs, Bios and project pages. Instructions for wiki posting and editing are available on the wiki site and will be reviewed in the seminar.


Interests of participatns

What are your particular interests in networks and complexity? If possible, let me know in advance at drwhite (at)

  • (x) Ethnography
  • (x) Social Networks/Sociology
  • ( ) Conceptual tools
  • (x) Methodological and computing tools
  • ( ) General social theory
  • (x) Organizational studies
  • ( ) Human-computer interaction, Internet, Computer supported cooperative work
  • (?) Historical analysis: Cities and trade networks
  • ( ) World system contemporary and historical analysis
  • ( ) Comparative studies
  • ( ) "Complex networks" and simulation
  • ( ) Other: ______

The initial readings will be expanded given the orientations and the problem areas of the participants. I.e. this page is still under construction in the early weeks preceding and into start of classes. Seminar participants should add readings (and their url links) for items they want to cover.

Theory and realism

If you are new to social network analysis, initial steps can be daunting. Its recommended that you begin from an introductory text. Some examples are Social Networks: An Introduction by Jeroen Bruggeman, Social Network Analysis: A Handbook by John Scott, and Exploratory Social Network Analysis with Pajek by Wouter de Nooy et al. The last book is the only text that initiate a beginner into a social network analysis software.

Basic Concepts

Social network analysis, trying to be precise, created a set of unique vocabulary. This is one of the main hurdles in comprehending its concepts. These were mostly extracted from Bruggeman so you are encourage to start from that book.

Actors -- Humans or organizations represented by nodes.

Adjacency matrix -- A matrix where rows and columns are mirror image of ties between pairs of actors. Only one type of relationships are shown in one matrix.

Affiliations -- Places or events where an actor can establish relationships. E.g. an event, a school, a workplace, and so forth.

Alters -- People related to an ego.

Arc -- A relationship with a directional property. E.g. 'A' loves 'B' but 'B' does not necessarily love 'A', direction from A to B. An oriented edge however only goes in one direction (nonreciprocated arc)

Assortive mating -- See homophily.

Assortive mixing -- Behavior where nodes get attached to nodes with similar number of ties.

Attrition -- A behavior where information is lost as its passed down in a social network.

Bridge -- A sole relationship connecting two components.

Clique -- A component with at least 3 actors and all actors connect to each other (complete subgraph).

Cohesion -- Usually estimated by density but in a strict sense this is incorrect, see structural cohesion or connectivity-k which is a true measure of cohesion.

Component -- A subset of a social network where every node is connected to every other either directly or through indirect paths. Also known as connected graph.

Connected graph -- See component.

Degree -- Number of relationships an actor has. See in- and -out-degree.

Density -- #Edges/MaxPossibleEdges in a component or graph. Density = x/maximum. For oriented graphs, maximum = n(n-1). For non-oriented graphs (symmetric arcs or 'edges' only), maximum = n(n-1)/2. The term 'graph' is typically used for non-oriented graph.

Diameter -- Longest geodesic in a graph.

Digraph -- A term for directed graph.

Directed Graph -- A social network which its relationships have directional properties. See Arc.

Dyads -- A pair; relationship where the direction goes both way. See arc and edges.

Edges -- Represented by lines without arrow head in social network diagram. Implies a two way relationship. See dyad.

Ego network -- A network of people surrounding a single ego, and their relationships. See alters. [requires verification]

Fractal network -- A network where actors are connected by repeated pattern throughout.

Geodesic -- Shortest path between any two nodes. See Geodesic of the entire network.

Geodesic of the entire network -- Mean geodesic of all nodes in a graph.

Graph -- A social network diagram. Or, in graph theory a set of vertices V and pairs of vertices E in VxV called edges.

Homophily -- A behavior where actors tend to connect with people similar to themselves. Also known as assortive mating.

Hub -- A node with a unusually large number of relationships.

Incidence matrix -- A matrix with actors in its rows and affiliations in its columns. See affiliations.

Lattice -- a set of nodes that is a partially ordered set with a binary operator ^ (meet) or v ('join') where every pair of nodes has a unique supremum as the closure of the operation. Thus if a and b 'meet' in c but also in d then c and d must also 'meet', and so on, ad infinitum. If ^ is an immediate supervisor of two employees a and b for example, and they have two such supervisors, there must be some eventual supervisor of supervisors that is unique. This is supervisory condition that can be used to define an organizational hierarchy. A (regular) lattice may also consist of lines that intersect (regularly), e.g., a two-dimensional lattice of orthogonal lines intersecting on a planar surface, a three-dimensional lattice doing so in a 3-dimensional space, and so forth.

Lines -- Represent relationships in social network diagram.

Local clustering -- Calculation is the same as density, but only an ego's and its alters ties are considered. See density and local clustering of entire network.

Local clustering of entire network -- Mean of all local clustering values. See local clustering.

Luck -- Might be used as the name of a parameter, e.g. 0 = no decays, 1 = maximum decay for a probability that decays with distance for a node establishing a relationship with another node.

Multigraph -- A social network that shows more than one type of relationships. Graphically, the lines are usually differentiated by colors.

Nodes -- Represent actors in a social network. Represented by Dots in social network diagram. (See actors)

Normal distribution -- Gaussian distribution, e.g., of number of relationships a node may have. Chance of a node having a large number of relationships is negligible. Used for relationships with high rate of decay.

Path length -- Number of ties between starting and ending nodes connected by a series of edges (directed or undirected).

Power law -- A probability generating function p~k\alpha governed by a power constant or exponent (typically alpha~1). If k is the degree (# links) of each node in a network and p governs a generating process for graphical evolution through adding edges (proportional to their degree), the network is called scale free and the network generated will also have a degree distribution in which the frequency of nodes with degree k that follows a power law p~k-\gamma. The power gamma for the generated distribution function will be larger than the exponent alpha in the generating equation (typically 2 < gamma < 3, and no greater than 3 for alpha of 1=preferential attachment). With power law distributions it is much easier, compared to the tail of the normal distribution, to find a node with many relationships. Many things obey power law, e.g. waiting time at clinic, number of friends, etc.

Power law with cutoff -- A Power law for fewer ties up to a cutoff where the distribution might become exponential, for example. This might reflect cases where relationships demand high maintenance, therefore each node can only have a certain number of ties. But the chance of find nodes of many relationships is still greater than normal because the lower part of the distribution is power law. Another type of power law cutoff occurs as a lower bound below which the distribution is no longer power law. All power laws must have a lower cutoff because no phenomena can become infinitely small (an all log scales go to infinitesimals).

Preferential attachment -- Behavior making the rich getting richer, and famous becoming more famous.

Relation - a distribution on pairs of elements (e.g., nodes in a network) which may be of three types: reflexive (loops for a node with itself), symmetric (aRb entails bRa), or asymmetric (not necessarily symmetric). An entire relation R may be reflexive (all pairs reflexive, with loops), symmetric, antisymmetric (no symmetries) or asymmetric (aRb may or may not entail bRa, also called nonsymmetric), transitive (aRb and bRc entails aRc), antitransitive, or nontransitive (also called a transtitive). A graph is typically defined as a symmetric irreflexive relation. A digraph is typically defined as an asymmetric irreflexive relation (edges are directed, i.e., arcs, which may or may not be reciprocated). An oriented graph is typically defined as an antisymmetric irreflexive relation. Many theorems in graph theorem are possible by excluding reflexivity, i.e., by defining edges and arcs as going away from the node rather than reflexive.

Searchability -- The ability for one node to find a target -- another node in the graph -- by means of some efficient (better than random) algorithm. For scale free networks this requires a beta parameter (see Power law between 2 and 2.5 (Lada Adamic et al 2003) for a hub search to be efficient (better than random search). In Kleinberg's (regular) lattice model for networks (of dimension 2, 3 or higher) a luck or beta parameter (between randomness and order) governing generation with additional links with distance decay, e.g., p~d-\beta so that beta=0 is random, and beta=2 makes a two-dimensional lattice optimally searchable while beta=3 makes a three-dimensional lattice optimally searchable, and so forth (i.e., the beta distance decay must match the lattice dimension so as to strike a balance of neither moving too far or too near in finding the target.

Solidarity -- A state in a social network where mutual expectations have developed. Implies stable relationships over a period of time. Related to cohesion.

Tie -- A generic term for relationships. Encompasses both edges and arc.

Threshold -- A predetermined minimal amount of interactions for social contacts to be considered a relationship. A predictor for emotional intensity.

Transivity -- A relation xRy between nodes xy is transitive if aRb and bRc entails aRc. This may be measure for triples abc by the ratio T = 3xTTriads / Connected triples. T = transivity. Triads = # of transitive triads in a graph. Connected triples = Number of triples in a graph that are connected (at least one path connecting abc).

Triples -- Connected Triples describes three nodes where there is a path between them but they they are not necessarily completely connected. In the general case a triple is any three nodes in a graph with whatever links they have between them.

Valued graph -- A social network where lines adopt a number showing its intensity. Graphically, the lines are usually differentiated by thickness.

Vertices -- See Nodes.

Communication Network

Communication networks in institutions were often ignored in the past, or developed around organizational control. But with availability of more ICTs, e.g. Internet, we are seeing growing importance of uncontrolled, informal networks, to acquire information critical to productivity ([1]). This has two implications for ICTs design: (1) ICTs need to support communication with external parties that support an institution's work, e.g. consultants, suppliers; (2) Traditional institutional structure maybe out-dated [2].

Traditional institutional structure maybe defined as one with departmentalized multi-functional workgroups. Engineers may form one department, and marketing, sales, and designs follow the same. Such workgroups face numerous problems in recent decades resulting in new development since the 1980s in collaborative styles. Some of these are the cross-functional team and agile software development. These are seen as improvisation to support information hungry teams to temporary increase their information 'bandwidth.' However, these measures are only temporarily as team members ultimately return to their respective functions.

[What are the advantages of functional teams? Efficiency, effectiveness for routine tasks. How routine are tasks in knowledge organizations?]

Borrowing from the triadic structure of social networks, what are the advantages if professions in project teams are organized, purposefully as such? Instead of relying on 'sociable' individuals to break the ice and do the job of cross-functional/hierarchical communication, which is problematic, how about purposefully organizing an organization by triads of different professions into highly connect web? But how dense is optimum?

Prompts: To what extent can ethnography, sociology, history, ..., ..., benefit from the theoretical and representational frameworks of networks and complexity?

Can these frameworks provide realism - and how is realism related to abstraction v. modeling? Can we leave the positivist concept of modeling behind?

Mutual dualities - to what extent are abstraction and instantiation-concretization mutual elements of theory?

Instance and time - what roles to structure, meaning, change, and dynamics?

<Empirical Formalism by Murray Leaf, Structure and Dynamics: eJournal of Anthropological and Related Sciences. Manuscript 1065.

Networks, ethnography, history, complexity

network ethnography and complexity

<Network Analysis and Ethnographic Problems> and its <Chapter 1> (starting on p. 32 of the pdf

networks and emergence

How malfeasance through networks constructed global markets: <Malfeasance and the Foundations for Global Trade: The Structure of English Trade in the East Indies, 1601-1833> Emily Erikson and Peter Bearman. American Journal of Sociology 111(6).


comparative ethnography, fractals, diversity

<The complex structure of hunter–gatherer social networks by Marcus J. Hamilton, Bruce T. Milne, Walker, Burger, and Brown. Proceedings of the Royal Society B (UK). 2007. Milne uses the Horton-Strahler branching ratio Senior author (last is often first) James H. Brown is known for <The fractal nature of nature: power laws, ecological complexity and biodiversity with Vijay K. Gupta, Bai-Lian Li, Bruce T. Milne, Carla Restrepo and Geoffrey B. West.

self-organization, culture and fractals

<Ron Eglash>. Recommended reading: African Fractals <articles self-organization course wiki <grad syllabus Complexity

<Ethnomathematics <Appropriating technology: Science in the vernacular

background on networks and complexity

An evolving lecture on <Complexity in human behavior>.

<Mark Newman, 2007. <Mathematics of Networks, in press (pdf), in The New Palgrave Encyclopedia of Economics, 2nd edition, L. E. Blume and S. N. Durlauf (eds.), Palgrave Macmillan, Basingstoke.

tracing longitudinal change through network blockmodeling

<"The Structure of Social Protest: 1961-1983." 1993. Bearman, Peter S. and Kevin D. Everett. Social Networks. 15:171-200.

2007 <Role Models for Complex Networks Jörg Reichardt, Doug White <submitted to European Physical Journal B

small worlds and complex networks

Watts, Duncan J. 2004. <"The "new" science of networks" Annual Review of Sociology 30:243-270.

Watts, Duncan J. 2003. Six Degrees: the Science of a Connected Age.

power laws, networks and complexity

Barabasi, Albert-Laszlo. <Linked}: <[ How Everything Is Connected to Everything Else and What It Means. Plume books 2003.

Complexity studies of terrorism, Lawrence Kuznar, 2007a "Rationality Wars and the War on Terror"; "Risk Sensitivity and Terrorism" 2007b.

<“On the Frequency of Severe Terrorist Attacks” <A. Clauset, M. Young and K. S. Gleditsch. Journal of Conflict Resolution 51(1): 58–88 (2007).

Fitting measures for distributions

alternatives to power laws and generalized complex networks

"power laws" from foragers to city networks fit a more general law or pattern: see <Fractals, Mandelbrot, self-similarity>, the <Tsallis q distribution project>, <Tsallis q historical cities and city-sizes> study group, <Social-circles network model>, and the (highly esoteric) <Robustness of the Second Law ... under Generalizations...>, etc.

planetary troubles

2007 <Growth, innovation, scaling, and the pace of life in cities. Luís M. A. Bettencourt, José Lobo, Dirk Helbing, Christian Kühnert, and Geoffrey B. West, <PNAS 104(17):7301-7306. <supplementary materials

The evolving lecture on <Complexity in human behavior>.

drw summer school lectures on networks, complexity and human history

Averting a Runaway Massive Planetary-Systems Breakdown White, Harrison (note to review: Haila, Yrjö, and Chuck Dyke (eds). 2006. How Nature Speaks: The Dynamics of the Human Ecological Condition. Duke University Press. <$22 as eBook

Stability domains group White, Harrison Studies


There are also older materials relevant to this seminar on a course site


Topical reports and reading discussions

Term project

Term paper

Human Complex Systems (HCS) Courses 2007

Undergrad, UCI, Fall 2007: Human Social Complexity and World Cultures

Grad Seminar, UCI, Fall 2007: Network Theory and Social Complexity

Undergrad, Grad: UCI, Fall-Winter-Spring 2007-2008: Course: social networks & complexity

Grad Seminar, UCI, Spring 2008 (taught at UCSD, UCI students by wiki and interactive video): Anthropological Models and Methods 2008

UCI eee pages

Undergrad, UCLA