# Network Theory and Social Complexity - Fall 2008

## Contents

- 1 Postponed to Winter 2009
- 2
**Network Theory and Social Complexity**Seminar - 3 Questions
- 4 Networks, ethnography, history, complexity
- 5 Self-organization
- 5.1 comparative ethnography, fractals, diversity
- 5.2 self-organization, culture and fractals
- 5.3 background on networks and complexity
- 5.4 tracing longitudinal change through network blockmodeling
- 5.5 small worlds and complex networks
- 5.6 power laws, networks and complexity
- 5.7 alternatives to power laws and generalized complex networks
- 5.8 planetary troubles

- 6 Links
- 7 Assignments
- 8 Human Complex Systems (HCS) Courses 2007

## Postponed to Winter 2009

This seminar will be taught later in the 2008-2009 academic year, probably winter

**Network Theory and Social Complexity** Seminar

A MATHEMATICAL BEHAVIORAL SCIENCE, SOCIAL SCIENCE, AND ICS SEMINAR

See: Network Theory and Social Complexity - Fall 2007 - 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

http://arxiv.org/abs/nlin.AO/0307015 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.

## Questions

### Interests of participatns

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

- (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^{} 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^{}. 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^{} 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).

## Self-organization

### comparative ethnography, fractals, diversity

<The complex structure of hunter–gatherer social networks by Hamilton, Milne, Walker, Burger, and Brown. Proceedings of the Royal Society B (UK). 2007. 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}: <[http://www.nd.edu/~networks/Linked/index.html 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

## Links

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

## Assignments

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