Machine Learning 10 601 Fall 2013 Network Models Eric Xing Lecture 22 November 18 2013 Reading See class webpage Eric Xing CMU 2013 1 Network Data Disease Spread Electronic Circuit Food Web Internet Social Network Eric Xing CMU 2013 2 Social networks Eric Xing CMU 2013 3 Information on a social network Social graph Friendship networks User ads network Text News feed Messages eCTR Link Intension Ads text Images Album Random posts Very high dimensional Non independent Insufficient training data this is true even we use the whole web Hard to optimize and interpret Ads figures Demographics Age occupation Eric Xing CMU 2013 4 Network analysis visualization Eric Xing CMU 2013 5 Visualization cont d Eric Xing CMU 2013 6 Global topological measures Indicate the gross topological structure of the network Connectivity Degree Path length Eric Xing CMU 2013 Clustering coefficient Barabasi 7 Local network motifs profiles Regulatory modules within the network SIM MIM FBL Eric Xing CMU 2013 FFL Alon 8 Models for Macroscopic and Descriptive Network Analysis A Random Networks Erdos and R nyi 1959 1960 P k e kk k k Mean path length ln k Phase transition Connected if p B Scale Free Price 1965 Barabasi 1999 P k k k ln k k 1 2 Mean path length lnln k Preferential attachment Add proportionally to connectedness C Hierarchial Copy smaller graphs and let them keep their connections Eric Xing CMU 2013 9 Summary Impressive graphs Seemingly impressive statements about nwk properties scale free small world Can even fit data with some models But What about details Can we infer e g the role of every node the meaning of every edge the network topology itself Can we predict Can we simulate Most current analyses tell BIG stories or obvious stories but not so useful to serious detail hunters Eric Xing CMU 2013 10 Dissecting Social Networks White et al From logical role systems to empirical social structures We can express a role through a relation or set of relations and thus a social system by the inventory of roles If roles equate to positions in an exchange system then we need only identify particular aspects of a position But what aspect Structural Equivalence Two actors are structurally equivalent if they have the same types of ties to the same people Eric Xing CMU 2013 11 Structural Equivalence Eric Xing CMU 2013 12 Structural Equivalence Graph reduced to positions Eric Xing CMU 2013 13 Classical Blockmodeling 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 Blockmodeling is the process of identifying these types of positions A block is a section of the adjacency matrix a group of structurally equivalent ACTORS Eric Xing CMU 2013 14 Cohesive Subgroups 1 2 1 1 2 1 1 0 3 1 0 0 1 4 0 1 0 0 5 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 3 1 0 1 0 0 1 1 1 1 0 0 0 0 4 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 5 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 6 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Eric Xing CMU 2013 1 2 3 4 5 6 1 0 1 1 0 0 0 2 1 0 0 1 0 0 3 1 0 1 0 1 0 4 0 1 0 1 0 1 5 0 0 1 0 0 0 6 0 0 0 1 0 0 15 Stochastic Cohesive Subgroups Domingo Carlos Alejandro Eduardo Frank Hal Karl Bob Ike Gill Lanny Mike John Xavier Utrecht Norm Russ Quint Wendle Ozzie Ted Sam Vern Paul Eric Xing CMU 2013 16 General Framework for Stochastic Blockmodel Regard each network tie as a random variable often binary Xij 1 if there is a network link from person i to person j 0 if there is no link for i j members of some set of actors N A directed network Xij and Xji are distinct A non directed network Xij Xji Formulate a hypothesis about interdependencies and construct a dependence graph The dependence graph represents the contingencies among network variables Xij e g defined on cliques i e a set of potential functions Eric Xing CMU 2013 17 The Hammersley Clifford Theorem Pr X x p x 1 exp c all cliques z A A where the summation is over all cliques A zA A xij A xij is the network statistic corresponding to the clique A is the parameter corresponding to clique A c X exp A AzA x is a normalising constant Besag 1974 Eric Xing CMU 2013 18 Bernoulli Blockmodels Suppose actors are either in block 1 or 2 and pairwise potentials Hammersley Clifford Pr X x 1 c exp i j ij xij Block homogeneity ij 11 if i and j both in block 1 ij 12 if i in block 1 and j in block 2 etc nominal constance Pr X x 1 c exp 11 L11 12 L12 21 L21 22 L22 where L rs is the number of edges from block r to block s Extendable to multiple blocks Eric Xing CMU 2013 19 Richer Network Tomography Multi role of every node Context dependent role instantiation Role dynamics Eric Xing CMU 2013 20 Mixed Membership of Actors Sampson s Monastery Sampson 1968 What are the factions How do …