Sunday 8 June 2014

Analogies between interconnected and clustered networks




FILIPPO RADICCHI
Indiana University
School of Informatics and Computing

VIDEO



Overview: In this talk, I will illustrate how spectral methods can be used to determine common properties shared by interconnected networks and graphs with community structure. In particular, I will show that degree correlations play a fundamental role for the characterization of the structural phases of these systems.


READINGS:
    Radicchi, F (2014) A paradox in community detection  EPL 106, 38001
    Radicchi, F (2014) Driving interconnected networks to supercriticality Phys. Rev. X 4, 021014
    Radicchi, F (2013) Detectability of communities in heterogeneous networks Phys. Rev. E 88, 010801(R) 




17 comments:

  1. Small question: at the beginning of your presentation you showed a graph of tennis players. Why was this a directed graph? If player A plays player B [so edge(A,B) exists], it is always the case that player B plays player A [so edge(B,A) exists] as well. Right?

    ReplyDelete
    Replies
    1. Hi Rachel,
      directions indicate the outcome of matches. A beats B is represented as B -> A. Edges are also weighted. If A beats B n times, then the weight of B -> A equals n. Note the reverse edge A-> B exists only if B beats A. If you apply this recipe to a certain amount of data (for example all matches of the year), you can construct a weight and directed network of contacts among tennis players. I used this type of networks to measure the "performance" or "prestige" of players with an algorithm similar to pagerank. Details and results are published in http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0017249 .

      Delete
  2. Comment calcule-t-on la probabilité d'être dans une sous-couche de réseau A ou B? Je n'ai pas saisi ce bout.

    Translation : How do you calculate the probability of being in layor A internetwork or layor B internetwork?

    ReplyDelete
    Replies
    1. In the model, the number of intra- and inter-layer edges are the same in both layers A and B. This means that the probability of being in one layer is equal to 0.5.

      Delete
  3. Very interesting talk! My first question for Professor Radicchi concerns his method for individuating networks in terms of dense interconnectivity and random walks. Contrast this with Professor Nishikawa’s analyses, which individuate structural clusters not in terms of interconnectivity but in terms common structural properties among nodes. How is this approach related to your own?
    My second question concerns the robustness of networks in cases of catastrophic cascades. Are there any particular meta-network properties that safeguard, or help protect, a network of networks from cascading catastrophes?

    ReplyDelete
    Replies
    1. The method presented splits the graphs into different clusters with a variation of the minimum cut method (see http://en.wikipedia.org/wiki/Minimum_cut).
      The method presented by Prof. Nishikawa looks at other properties and i more general. There are no simple analogies between the two methods.

      Intuitively, you can expect that the multilayer network is a safe state when is indistinguishable from a non layered network, and subjected to catastrophic failures when in the decoupled or bipartite phase.

      Delete
  4. This question may be basic or naive, but I didn't exactly understand the difference between a "well-defined" network vs an "ill-defined" network. What characterizes each one? Are dynamics taken into account? Is it just based on interconnectivity or do structural properties are taken into account too? What's the role that "detectability plays in all this" I got a little lost. Can you give a real-life example in which you can differentiate between the two (ill defined vs well defined)?

    ReplyDelete
    Replies
    1. Ok, so now I see that the ill-defined have more connections outside than inside the comunity. Still, how is this related with detectability? I still haven't be able to understand that.

      Delete
    2. The typical definition of a community is a group of nodes with a density of internal connections than the density of external connections. If each node in the community has more connections inside than outside, then this can be viewed as a "well-defined" community. If the former is not true and many nodes have more connections outside than inside, then this group can be viewed as an "ill-defined" community.

      Delete
  5. Networks modeling with random variables is a probabilistic approach. What’s would be main differences, advantages, inconveniences of networks modeling with a possibilistic fuzzy approach? Fuzzy network modelling is more easy to interpret and communicate?

    ReplyDelete
  6. Could you explain me more about the paradox contradiction community, please? Thank you FILIPPO RADICCHI.

    ReplyDelete
    Replies
    1. I didn't really get it, I would like to know more about it as well.

      Delete
  7. You talked a lot about networks of networks and interconnectivity, but you only mentioned interconnectivity between transportation, gas, power, etc. What about interconnectivity between humans and machines? What do you think of the extended mind/ the global brain?

    ReplyDelete
  8. I’m terrible in mathematics and I don’t understand how we could build a system based on random. I was really impressed to learn that there is method that takes random into account and that is able to include dynamic of communities.

    ReplyDelete
  9. I enjoyed the map showing gas, power, transportation and other inter-network connections. I imagine that visualizing these interactions is only becoming more important as our infrastructure increases in complexity. Are researchers, or government employees working on developing easy visualizations of infrastructure networks? This knowledge could help inform decision regarding pipeline placement and more.

    ReplyDelete
  10. Raddici makes an analogy between thermodynamics of any given substance and the nature of interconnected networks. I wonder if graphs or networks are powerful enough to represent physics in general. He also talks about phase transitions, and anomalous behaviour driven by exogenous activity.This reminds me of Heylighen's conception of self-organization. By his description, agents are also not isolated but interact in a larger network. Environmental influences can drive changes in state, depending on feedback loops and alignment. These concepts translate very well into a network framework. A real network is the result of an evolutionary process – it exists in the face of increasing entropy because it has some ability to maintain a structure. Because of this, it is coherent in some way, and it tends to actualize in a particular way through the definition of its goals and intentions. So we can think of network communities through this behaviour as agents. These agent communities interact and in some cases self-organize through the alignment of goals/intentions creating an amplifying feedback loop. This induces a phase transition. The transition plateaus in a new state when friction with some other functional entity is met. In light of this, I wonder how we can understand the paradox of community detection (detection of well-defined modules is more difficult than the identification of ill-defined communities) in these terms.

    ReplyDelete