School and Workshop on Structure and Function of Complex Networks: forth day

In the following some comments about the Program of the forth day.

[The following comments are probably understandable/useful only to me, since they are quickly written and cover only the main concepts I wanted to carry away for sure from a lecture. I post them here anyway but you’ve be warned]

The structure of biological networks
Reka ALBERT
Pennsylvania State University, University Park, U.S.A.
Fascinating! Have a look at the lecture notes. They were really interesting. the topic was biological networks: 4 kinds of them.
(1) Protein-protein network (for example, of yeast). There is powerlaw in yeast, c.elegans, …
I was feeling the sense of progress, the sense of “wow, we are riding on the big wave and nobody knows what will happen in few seconds…” It really seems that this is a topic where you can have an impact worldwide, it is so rapidly evolving and so young! You do really build on the discoveries made by other people few weeks before!
(2) methabolical networks
TODO: I need to read “survey models of net formation: stability and efficiency”
what is really interesting of biological networks is that there isn’t a single way to map them in networks but many, many, many…
(3) transcription networks
(4) signal transduction pathways:
Are there public databases? some: aligning cells, KIGG, … Are they already digested? no you need to preprocess them to extract what you want
Feeling: Reka said many times “it will get better”, meaning our coverage of data and understanding of genome and biological information. Note for example that the actual coverage of the genome is 10%/20%! and between different datasets (independently collected but representing the same genome, for example yeast) there is an overlapping of only 7%!!! Research is really on the edge!

Epidemic spreading
Alessandro VESPIGNANI
Indiana University, Bloomington, U.S.A.
Great talk again! Indiana seems really a great university.
Open problem: why viruses remain active for years? Theoretically lambda_c=1 for every virus and this is not possible. [I’ll try to get the slides…]
keywords for later study: mean field theory, first order parameter, second order parameter, immunization thresholds, use local knowledge for immunization threshold (similar to local trust metrics that use local knowledge: TODO need to think about it)

Physical Internet
Alessandro VESPIGNANI
Indiana University, Bloomington, U.S.A.
Keywords: toMography, since you cannot know all the connection of a router, you have to resort to traceroute-like way of discovering the topology (never thought about it before!). [Parallel thought: routers are like peers in a p2p system. for p2p systems it was reported that users chagne the open source code or reverse engineered the closed source code to change the behaviour of their peers and this produced an instable-nobody-knows-what-is-happening-in-the-complete-netowkr phenomena. Could the same happen for Internet? Well, of course, router administrator are not scruffy hackers that like to play with the code of the routers but at least in principle…]
Small world of internet: mean distance for routers=10, mean distance for ISPs=10.
Assortative and disassortative.
Crovella et al 2002: take a random graph, do traceroute probing and you see a powerlaw, and not the expected POISSON distribution! aaaaarggh! are powerlaw just a flaw in our way of measuring stuff?!? luckily not but pay attention to all those details otherwise you produce non-scientific results! [clauset and Moore, 2004]. Check DIMES (decentralized probing of the internet).
[Note for myself: CRTL+C & CRTL+V is in general illegal in Internet, where everything is copyrighted (all rights reserved) by default].

Social networks
Stan WASSERMAN
Indiana University, Bloomington, U.S.A.
He is a sociologist and statisticians and has a different take on the all matter (for example, he started with some cartoons: “See you in the funny pages” of linton freeman). I like it. Diversity is always good. He showed many friends networks (TODO: find the data). Suggested to subscribe to INSNA mailing list (I already am, in fact I’m here because of an email he sent on this mailing list!). Showed very expressive networks (for example the evolution in time of friendship relationships between child in a school: 1st grader, all connected; 5th grader, boys and girls divided, boys all friends (high degree), girls much much less, some arrows from girls to boys, no arrows from boys to girls .. an image says more that 1000 words sometimes). This networks are called cross-sectional.
He showed some different studies on a network of florentinian families: an edge could represent when a member of family A married a member of family B. An edge could represent a business relationship. He showed different visualizations of the networks and different measures.
Unsuprisely, prominents families are very well connected.
Path: a->b->c
Walk: a->b->c->b
Cycle: a->b->c->a
Strong component= {a,b} a->b and b->a
Weak component= {a,b} a->b (edges in one direction are enough)
Some single values that can be computer for an entire graph:
– Centrality represents roughly the variance of centrality scores.
– degree centrality (homogeneous=1, dishomogeneous=0), closeness centrality, betweenness centrality.
Possible TODO: shows centrality on Italian politicians (it could lead to interest results).
Possible TODO: consider as nodes countries and model their relationships; it should be plenty of data (import/export flows of different products [oil, agriculture, weapons, …], diplomatics exchanges, people migration flows), with their evolution in time.
Check “Prestige Rank”. Cna we model your beliefs based on your networks? … what about controversiality?

Modelling the dynamics of biological networks
Reka ALBERT
Pennsylvania State University, University Park, U.S.A.
lecture notes
Second part of morning talk

Strategic models of network formation: stability and efficiency
Matthew G. JACKSON
California Institute of Technology, Pasadena, U.S.A.
Game theoretic model of network formation.
Economist approach…
Agents get utility based on their position in the network.
Check slides.
TOTHINK: can pagerank value be considered as a payoff in network?
TODO: check Bala and Goyal (2000) that consider directed networks. What about weighted?
Understanding if society can move away from a local minima nash equilibrium –> if there is forward thinking, it is possible to realize that if I move from corrent state to another (to maximize my instant payoff), it can be the case that also the other players will change their actions and we will all be worst off. Well, it reminded me of one of the last scenes of the movie “War Games”.
TODO: check “corominas bosch (2002)”
An external entity can change the payoffs of players: used to model a governments that can tax (subtract Tij) or give subsidies (add Tij). Example: government exiges from telephone companies that they wire also people that are very far away from cities; this produces a model in which, in a sense, telephine companies “tax” people in the cities and “subsidy” people out of cities. This means that regulations external to the “free” market (i.e. laws) are required to move the entire society into a state that is not a nash equilibrium, but that is possibly more equally fair for every single agent.
Can we model the economic market as a small world? Yes, (1) model low cost for forming local connections/links –> high clustering, (2) high value for distant connections –> low diameter, (3) high cost for distant connections –> few distant links; this is essentially the watts-strogats model that creates small world networks.
TOTHINK: collect the dataset of relationships between CEOs of different megacorporations (from theyrule.net, the data should be public) and do something: being in more than 1 board leads to …, centrality means that …, …
I wrote on the notes (but not at all sure where I got this info or if this is correct) that 40.000 new papers are created every single day (in a single discipline), of course nobody can process this new info. Find what NetworkBench is.
TODO: correlation between overlapping and similarity.

Network Visualization
03h00′
Katy BORNER
Indiana University, Bloomington, U.S.A.
3 hours computer session (hand-on) in which we played with different tools and different dataset, very very interesting!
Lecture notes

Leave a Reply

Your email address will not be published. Required fields are marked *