CS 789 THEORY SEMINAR [home]

joint with MICROECONOMIC THEORY Workshop

Speaker:    Matt Jackon
Affiliation:  CalTech
Date:          November 15, 2004
Time:          4-5:30
Place:         Uris Hall 498

Title:          Search in the Formation of Large Networks:
How Random are Socially Generated Networks?

Abstract: 

We present a model of network formation where entering nodes ¯nd other nodes to link to both completely at random and through search of the neighborhoods of these randomly chosen nodes. This is the ¯rst model of network formation that accounts for the full spectrum of features that characterize large socially generated networks: (i) a
small diameter (maximal path length between any pair of nodes), (ii) high clustering (the tendency of two nodes with a common neighbor to be neighbors), (iii) an approximately scale free degree distribution (distribution of the number of links per node), (iv) positive correlation in degree between neighboring nodes (assortativity), and (v) a negative relationship between node degree and local clustering.

We fit the model to data from four networks: a portion of the www, a co-author network of economists, a network of citations of journal articles, and a friendship network from a prison. Besides offering a close ¯t of these diverse networks, the model allows us to impute the relative importance of search versus random attachment in link formation. For instance, the fitted ratio of random meetings to search based
meetings is seven times higher in the formation of the economics co-authorship network as compared to the www.

See also the full paper.