SOC SCI 289 NTWK THRY&SOC COMPL fall 2010 sem B (72710)

From InterSciWiki
Jump to: navigation, search

Network theory for MBS, Sociology, Computer Science, and Business School, Tuesday 9-11:50 SSPA 2142 - Contact instructor for info to add Fall 2010 network seminar. 3 MBS, 3 Sociology, 2 othrs


David Easley and Jon Kleinberg. 2009. Networks, Crowds, and Markets: Reasoning About a Highly Connected World

Easley Kleinberg.jpg

Bruggeman, Jeroen. 2008. Social Networks: An Introduction. Routledge.

Network Theory and Social Complexity Seminar


See: Network Theory and Social Complexity

Benoit Mandelbrot -- on-line talk, reviews, summaries of 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 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))

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 participants

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

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.

Belief in Moralizing Gods -- 2010 4 Submission. Scott D. White, Douglas R. White, Tolga Oztan, Ren Feng. Exploratory causal analysis for networks of ethnographically well-studied populations (Evil eye) (Moralizing gods)
  • back in China: Ren Feng Soc - Causality, South Indian transformations - Public policies management

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.

Problems of Structure, Dynamics and Causality

E.g., the problem with the new books of John Levi Martin, is that structure is assumed to simple gell out of repetition, and it is concrete interaction and local structure, not emergence of more global structure interacting with local structure, that leads to the appearance of structural dynamics, but no means of testing causality. Many of his assumptions are merely opinions and are not empirically justified. In contrast:

Judea Pearl's causal graphs

Simplicity (e.g., Methodological individualism) and Complexity (e.g., Global and local structure)

Definition of multilevel network as system

Definition of complexity as a system of units as beginning with the ratio of internal delay time in unit response to interaction time between units.

The "complex structure of forager social networks" is a good candidate for causal network analysis. The authors note (2007:2195) "Complex systems composed of multiple interacting parts tend to self-organize or evolve structures that maximize whole-system performance by optimizing among the intersection of components."

Peter S. Dodds, Duncan J. Watts, and Charles Sabel. 2003. Information exchange and robustness in organizational networks. Proceedings of the National Academy of Sciences, 100(21):12516-12521. - A model of how supervisory and lateral information interacts with production chains, also suggesting (to Duran Bell) that offshoring production to cheap labor has negative consequences for the R&D - production chain efficiency.


Network Models

General (outline from Ronald Burt 1988)

Order: Theory of the Dag

e.g., 2010 SSHA ppt Network-inclusive Fitness :�Kinship networks from social and genetic perspectives, 2010, Doug White
(Dual) Galois lattices
Entailment analysis
e.g., Sexual Division of Labor


Structural cohesion = Cohesive blocking
Pairwise k-cohesion (White-Newman) multiplied by binary graph = cohesion graph - done in UCI net
Clique and k-core percolation
Lattice of Cliques
Bipartite cliques and Galois lattices
2006. Faster Algorithms for Constructing a Galois Lattice, Enumerating all maximal bipartite cliques (of a bipartite graph)

Role Equivalence

Regular (REGGE algorithm


Bonacich centrality
Flow centrality


Bridges to diversity


Structural holes
Structural folds


Zipfian and power law Preferential attachment
Social-circles network feedback model, see Social-circles network feedback model#Retrofitting

Small worlds

Milgram experiment
Connectivity phase transition: Erdös-Rényi random graph, others
Social circles - Feedback model

Resilience (Preservation of structure under node deletion)

Hub deletion resilience
Random node deletion

Dynamical transitions

Turchin, Peter. 2003 Evolution in population dynamics. Nature 424: 257-258.
Turchin, Peter. 2005 Dynamical Feedbacks between Population Growth and Sociopolitical Instability in Agrarian States. Structure and Dynamics 1(1): 49-69.
Tipping points and phase transitions (Positive feedback)

Field specific (outline from Melanie Mitchell 2009) - see Soc_Sci_289_html_links_to_articles


Genetic regulation

Metabolic networks

Epidemiology James Holland Jones

Ecologies and food webs

Citation networks

Basic Concepts and Metrics

See for example Power law Zipfian generator

Social network analysis, aiming at precision, initiated a set of shared formal 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.

See: Wikipedia:Social_network#Metrics_(Measures)_in_social_network_analysis

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 only goes in one direction (nonreciprocated arc)

Assortive mating -- See homophily.

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

Attrition -- A behavior where information is lost as its passed down in a social network. May be compensated by within cohesive sets of nodes.

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 relative density (e.g., "community detection") but in a strict sense this is incorrect, see structural cohesion or connectivity-k which is a true measure of cohesion. NetWiki CommunityDetection browse: A nonparametric view of network models and Newman–Girvan and other ... large networks by Aaron Clauset, Mark Newman, and Cristopher Moore

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.

Disassortive mixing -- Behavior where nodes get attached to nodes with contrastive numbers of ties.

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. Alters are those in an ego's network, and the number of algers is ego's degree.

ERGM -- Exponential Random Graph Models, which estimate with (See:) motifs at a smaller scale within the graph that are randomly combined in different proportions to compose the entire graph. Robins (2009) MCMC for ergm reviews "exponential random graph models, a family of statistical models for modeling social networks. Full model specification requires formulation of a dependence hypothesis which proposes how possible network ties are conditionally dependent on each other. The dependence hypothesis in effect sets out the processes whereby network ties self organize into small micro-structures (network configurations). These can be construed as the building blocks of the global network structure. The paper presents three dependence assumptions that result in different types of graph distribution: (1) Bernoulli graph distributions whereby ties are assumed to be independent of each other; (2) Markov random graph distributions whereby ties are assumed to be conditionally dependent if they share a node; and (3) social circuit dependence where dependence emerges from observed ties, such that two possible ties become dependent if their observation would create a four cycle." See: Markov random graph as estimators.

Exponential distribution -- (negative exponential distribution), a continuous probability distribution that describes the times between events in a process in which events occur continuously and independently at a constant average rate (Poisson process). E.g., "a good approximate model for the time until the next phone call arrives" betweeb 2-4 pm" or "until a radioactive particle decays." Empirically, such a distribution tends to be linear is semi-log while a power law tends to be linear in log-log. See: [[Aaron Clauset] for a reference on the problem of curve-fitting for empirical univariate distributions.

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

Geodesic -- Shortest path between 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. E.g., 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.

Motifs -- Smaller subgraphs within a network whose frequencies can be censused and modeled by ERGM or other models.

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 for a node establishing a relationship with another node, e.g., 0 = no decays, 1 = maximum decay for a probability that decays with distance.

Markov random graphs -- defined by a particular dependence structure between network ties... see ERGM

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

Multilevel graph -- a network in which a node at one level may contain a network of relations at the next level. Use for a complex system, for kinship networks, e.g., links between families that contain individual members as defined by Bourbaki algebraist André Weil and used by White, Jorion, Houseman and others.

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. May apply to 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 distribution -- An hypothesis about a univariate distribution that is linear in the log-log plot of an interval or ratio-level variable logged on the x axis (e.g., network degree of nodes) and log of frequencies on the y-axis. Clausett, Shalizi and Newman (2009) provide software for rigorous inferential statistical tests needed to establish this property of a univariate distribution as against other distributions of high variance (Zipfian and “power law”, Yule-Simon, etc., where the mean is not representative of most samples) and low-variance (Gaussian or Normal, exponential, Maxwell-Boltzmann, Raleigh, etc.). Zipf's is the special case where the product of rank by frequency is constant in a frequency distribution.

Power law generator -- A probability generating function p~k\alpha governed by a power constant or exponent (typically alpha~1). (Note that the alpha of the generating function and the log-log slope of the generated distribution will differ). 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 distribution 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 Zipfian generator -- The mathematics of Zipf - having the properties of successive occurrences of "a system with an unbounded number of possible states", "expected for a system evolving to a stable state between order and chaos." Bernat Corominas-Murtra and Ricard Solé 2010, "Universality of Zipf's law", Physical Review E, 82:011102 abstract. Zipf's is also analogous to the special case of a frequency power-law distribution where the product of frequency by quantity (or by rank in the Zipf) is constant.

Power law with cutoff -- A Power law for the lower part of the distribution (degree in a network: 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 -- A network attachment process for nodes, proportional to past attachments, e.g. "rich get richer", "fame begets more fame", etc. Albert-László Barabási <Linked> falsely attributes a preferential attachment process to networks with a power-law degree distribution, but there are many other generative processes for this feature that he fails to consider.

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 atransitive). 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, for example.

Transitivity -- A relation xRy between nodes xy is transitive if aRb and bRc entails aRc. This may be measured for triples abc by the ratio T = 3xT_Triads / 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 Networks- an interest of Yong Ming Kow, 2007 and other items

Julsrud, Tom E. 2007 Core/periphery Structures and Trust in Distributed Work Groups: A comparative case study. Structure and Dynamics: eJournal of Anthropological and Related Sciences 2(2)

Yong Ming: Communication networks in institutions were often ignored in the past, or developed around organizational control. But with availability of more ICTs (e.g. the Int'l Test Commission rules for the 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? See empirical formalism.

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

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?

R&D Networks - of interest to Michael König

Nobuyuki Hanaki, Ryo Nakajima, Yoshiaki Ogura. 2008 The dynamics of R&D network in the IT industry Research Policy 39 (2010) 386–399.

Networks, ethnography, history, complexity

Key players

Ballester, Coralio, Antoni Calvó-Armengol & Yves Zenou, 2005. "Who’s Who in Networks. Wanted: The Key Player" Econometrika 74(5):1403-1417.

network ethnography and complexity

networks and emergence

Emily Erikson and Peter Bearman. 2005. 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> American Journal of Sociology 111(6).


comparative ethnography, fractals, diversity

Pages from Marlow hunter-gatherers and human evolutionMap.png

Binford forager data - and a review by Stephen Shennan. 2004. Forty Years On: Review of Binford, Constructing Frames of Reference. Journal of Human Evolution 46: 507-515. Shennan emphasizes the fit of Binford's views and findings to Optimal Forager Theory (OFT). OFT has also been applied to robberies in Los Angeles and many other problems, from simple decision-theory propositions.

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

structural folds

Structural Folds

network dynamics

background on networks and complexity

An evolving lecture on <Complexity in human behavior>.

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

balance and clustering in signed graphs: local and global

Signed graphs

***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.

Jörg Reichardt, Doug White. 2007. Role Models for Complex Networks 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

Barabási, Albert-László: <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 projects

Term paper

New links & refs

Daniel Dorling, Mark Newman, Anna Barford, 2008. The Atlas of the Real World: Mapping the Way we Live Hardcover Visit Amazon's Daniel Dorling Page.

Soc Sci 289 html links to articles

Human Complex Systems (HCS) Courses 2010

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -