Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Earth Biotech Science

PageRank Algorithm Applied To the Food Web 94

An anonymous reader brings word of a new application for PageRank, Google's link analysis algorithm: monitoring the food web in an ecosystem. A team of researchers found that a modified version of PageRank can predict with great accuracy which species are vital to the existence of others. Quoting: "Every species is embedded in a complex network of relationships with others. A single extinction can cascade into the loss of seemingly unrelated species. Investigating when this might happen using more conventional methods is complicated, as even in simple ecosystems, the number of combinations exceeds the number of atoms in the universe. So, it would be impossible to try them all. Co-author Dr. Stefano Allesina realized he could apply PageRank to the problem when he stumbled across an article in a journal of applied mathematics describing the Google algorithm. 'First of all, we had to reverse the definition of the algorithm. In PageRank, a web page is important if important pages point to it. In our approach, a species is important if it points to important species.'"
This discussion has been archived. No new comments can be posted.

PageRank Algorithm Applied To the Food Web

Comments Filter:
  • by Anonymous Coward on Friday September 04, 2009 @10:19PM (#29320135)

    Pagerank is just a repeated application of a transformation matrix. It has the effect of running a Markov model (a way to model discrete states) until there is convergence. He just used a Markov model the way that it is supposed to be used...

    I dont get it... what's notable here?

    • I dont get it... what's notable here?

      We're finally able to figure out what species will have the most impact if it is removed. Likely, the folks at google are turning this into some sort of biological warfare device - They want to figure out which species of mosquito we have to kill in order to remove all mouth-breathers from the planet, leaving all the hot women alive for the rest of us.

      More seriously, if we can figure out which species are most important (and which are least important), doesn't that give both the tree-hugging sea-kittens a

      • Likely, the folks at google are turning this into some sort of biological warfare device - They want to figure out which species of mosquito we have to kill in order to remove all mouth-breathers from the planet, leaving all the hot women alive for the rest of us.

        Hey, hey, what's with all this "us" stuff?

    • by xenocide2 ( 231786 ) on Friday September 04, 2009 @11:17PM (#29320403) Homepage

      It's remarkable because a biologist discovered math and possibly statistics.

      • Re: (Score:2, Funny)

        Actually the Markov model is prevalent in bioinformatics, as well as other statistical methods. However, the biologists are an entirely different race, typically unfamiliar with advanced mathematics. In fact, the entire field of biology works on foundations and culture so alien to science (fondness for objectivity and modesty) sometimes I wonder whether it is right to call them scientists, or just group them with the social scientists and psychologists.

        It's a pity they dominate the big science journals.

        • by Teancum ( 67324 )

          In fairness to biologists, their science has only recently (compared to other sciences) become a "hard" science with strong foundational theories and strongly determinant principles that could be applied to arrive at a conclusion. Largely, it still is in the fuzzy region between the hard sciences (like physics and astronomy) and the social sciences (like anthropology and psychology). I've even seen biologists use anthropological tools and study methods when investigating animal behavior, to give an exampl

          • by Teancum ( 67324 )

            Excuse the screwup I just had with the above section. Firefox just re-located a sentence I had intended for the last paragraph that ended up in the first one. Oops.

      • Isn't that a sign of the apocalypse?
      • Re: (Score:3, Informative)

        by speedtux ( 1307149 )

        Mathematical biology has a history that goes back further than computer science. Many biologists probably know a lot more math and statistics than your average computer scientists.

        • On the other hand, I've seen biologist written perl code [oxfordjournals.org] that terminated on div-by-zero, and closed, re-opened then seeked into the input file rather than implement a linear processing of data. I've also met plenty of biology grad students who basically said their technique for analysis was to invite a statistics co-author. If you're going to claim Mendel as a mathematical biologist, we might as well call Babbage a computer scientist, and he built the diffrence engine 30 years before Mendel's pea experiment

      • Not to mention SEO and PR... he must be reapplying for funding soon!

    • by DeadDecoy ( 877617 ) on Friday September 04, 2009 @11:17PM (#29320405)
      Because it's a novel use of an existing method? It was published in PLoS and not some mathematics journal. So, while the algorithms are not new, they may be new to the intended audience. The actual claim of the article is that it can offer a predictive analysis of extinction rates of a species and validated them on some in-silico experiments. This could be useful for bench-scientists, as they could figure out what might happen in an experiment before running expensive tests. This might be useful for conservations trying to make sure whole ecosystems don't die out due to the removal of a species; the 'might' is significant as real-world ecosystems are generally more complex. But anyways, it's interesting because the models have practical application outside of theory to help us understand the world.
      • by jpmorgan ( 517966 ) on Saturday September 05, 2009 @01:37AM (#29321095) Homepage
        Yes, it is notable that this wasn't published in 'some mathematics journal'. Pagerank is computing the limiting distribution of a discrete-time markov chain applied to webpages using a certain statistical model of hyperlinks. It makes no sense to talk of applying 'pagerank' to things other than webpages, because that's what makes pagerank special! As soon as you take pagerank out of the web-context, it's just a steady state analysis of a markov chain, which is a standard statistical technique covered in undergraduate statistics courses. It's like saying applying bayesian inference to a problem in ecology is using a 'spam filter.'

        For me, this tells me that perhaps these researchers should wander over to their local mathematics department more often. They might find all sorts of goodies that mathematicians have developed in the past few centuries. Dr. Allesina might have discovered that there was no need to reverse engineer the algorithm, since the underlying mathematical principles have been well understood for over a hundred years. We might have a better understanding of the world if most sciences took mathematical models as seriously as physicists do.
        • Quite so. The problem with PageRank is that it's quite a crude approach to simulation, in fact. The steady state distribution is just an average, whereas we already understand how to do so much more, eg looking at the sizes of random fluctuations and maxima and minima.

          It would be good if these biologists who are impressed with this example were to read a book about Markov processes, or took a postgraduate course in stochastic processes. This isn't rocket science, it's quite commonly used by engineers, phy

    • No, you're right. It's not notable. Whenever one area of knowledge is improved, every other area is instantly aware of this discovery and can utilize it with 100% efficiency right away.

      Less sarcastically, I am not surprised a biologist is unaware of such mathematical models. It's notable for the fact that they're applying a rather simple method to a rather old problem and it's extremely effective.
    • i am also qant to know the pagerank algorithm !may be you need to find a seo .http://www.igolfyoo.com
    • Because it's an improvement of the old eBay feedback system biologists were using before. They found that system was open to "retribution" feedback if the prey didn't rate the predator highly enough.

      Review by vole:
      (positive) Fox was an excellent predator!!!! Would be eaten again!!!!! A+++++++++++!!!!!

  • by JordanL ( 886154 ) <jordan,ledoux&gmail,com> on Friday September 04, 2009 @10:20PM (#29320143) Homepage
    What factorial does it take to equal that number? I know that its very easy in math to get numbers that large, but this wasn't a place I expected to find it.
    • Re: (Score:2, Interesting)

      by cmseagle ( 1195671 )

      Yeah, I would tend to call BS on that particular statistic. Let's say the average water bottle is .5L. In that one, single water bottle that is sitting on my desk, there are 5.01*10^25 atoms. That's one hell of a number.

      Now, let's pretend God has a really good magnifying glass and a really small set of tweezers, and he's removing atoms from this water bottle at a rate of 1 per second. Conservative estimates put the universe at 13.5 billion years old, which converts to 4.25*10^17 seconds.

      So, since the

      • by MyLongNickName ( 822545 ) on Friday September 04, 2009 @11:43PM (#29320549) Journal

        What does your tweezers and removing atoms have to do with combinations? It is trivial to come up with a situation where there are more possible combinations that atoms of the universe. The number of possible chess games starts to get close (magnitude of 50 versus 80 for the atoms in the universe. Slightly more complex scenarios would easily go past 10^80. The trick is to find a way to model the complexity with a much simpler algorithm.

        • Are more obvious one would be the different sequences you could make from all the atoms in the universe.
    • Re: (Score:3, Informative)

      Here ya go [wordpress.com]. About 59.

    • Re: (Score:1, Informative)

      by Anonymous Coward

      According to Wikipedia, [wikipedia.org] our best estimate of the number of atoms in the universe is 10^80. The smallest factorial greater than this number is 59! = 138 683 118 545 689 835 737 939 019 720 389 406 345 902 876 772 687 432 540 821 294 940 160 000 000 000 000 = 1.39 * 10^80. (The next smallest factorial is 58! = 2 350 561 331 282 878 571 829 474 910 515 074 683 828 862 318 181 142 924 420 699 914 240 000 000 000 000 = 2.35 * 10^78.)

  • by Anonymous Coward

    A species is more important if it points to my stomach.

    Also see my upcoming research topic:

    Bioinformatic Algorithm for Standard Texan-Americans with Retro-Dissonant Suppositions

    I expect to prove that BASTARDS are essential to the American way of life.

    • by TheLink ( 130905 )
      > A species is more important if it points to my stomach.

      Especially if it points using a very sharp spear, or a shotgun. Then you can really talk about extinction and things "vital to the existence".
  • Importance (Score:3, Interesting)

    by Darkness404 ( 1287218 ) on Friday September 04, 2009 @10:44PM (#29320243)

    In PageRank, a web page is important if important pages point to it. In our approach, a species is important if it points to important species.'"

    The difference is, its pretty obvious to a human if a page is important. On the other hand there are a lot of species that we don't know if they are important or not. So how do we know what the "important" species are? Other than humans, we don't know of any real "important" species. Could the ecosystem survive without X? Theres no way we can really know that.

    • Have you learned nothing from history? We can know if an ecosystem survives without certain members.

      It just isn't a good idea to experiment.
      • Re: (Score:2, Troll)

        Well of course, we know that above all things nature simply survives. But we can't know for certain whether they are "important" for it to survive on its own. Especially with the ever-changing nature of the world. If a predator dies will another predictor eaten by the other predator move in? Will the prey multiply like crazy? Its these things that will make the PageRank algorithm useless in biology.
        • Its these things that will make the PageRank algorithm useless in biology.

          I suppose you're right. Since you disagree, the entire idea must be without merit.

    • Re:Importance (Score:4, Informative)

      by JorDan Clock ( 664877 ) <jordanclock@gmail.com> on Friday September 04, 2009 @11:29PM (#29320475)
      The model helps determine if a species is important. That's the whole point. Previously, we didn't have an easy way to determine a particular species impact on an ecosystem until it was almost extinct or already gone. Now by using "PageRank" to determine their importance, we can model what will happen if specific species are no longer part of the food web.
      • Re: (Score:3, Insightful)

        I was worried about this. Either underspecifying "importance" or using it in a simplistic way (though you may not actually be doing these things).

        It measures a kind of importance. Not importance in all respects. Specifically, it measures importance in interdependence. Which only very roughly translates to an idealized general or universal importance.

        Remove humans from the web and you won't get much "impact on [the] ecosystem" (in the form of cascading die off). Yet humans are generally regarded as "imp

        • The idea of saving an animal based on its appearance is one of the reasons why many animals receive a disproportionate amount of funding. There are some species of animals that have more money diverted to them than hundreds of other species combined for no other reason than they are more marketable.

          If pandas go extinct, what effect would it have on the ecosystem? Almost none. It eats bamboo for 99% of its diet and I doubt it eats enough to be a source of control on the growth of bamboo. However, pandas are
          • The plumage comment was a joke, sorry. I was trying to be ludicrously shallow, but the truth is that beauty actually does count for something.

            The value of life is not simple, so it's not easy to put it simply. For example, it's not clear to me what "good for the ecosystem" means. It sounds like maybe it means "tendency to preserve the extent (quantity?) of food/consumer relationships" or maybe "tendency to preserve maximal living mass" or maybe "tendency to promote diversity". This is real philosophical

    • PigeonRank (Score:3, Funny)

      by FooAtWFU ( 699187 )
      I would have thought that an animal-based algorithm such as PigeonRank would be more applicable to this problem.
    • Re:Importance (Score:5, Informative)

      by Hadlock ( 143607 ) on Friday September 04, 2009 @11:57PM (#29320625) Homepage Journal

      NO! Page Rank is not named after webPage. It's named after Larry Page who created it. Arrrgh.

  • by Kligat ( 1244968 ) on Friday September 04, 2009 @10:51PM (#29320285)
    I've often been annoyed by the excessive focus on the iconic [washingtonpost.com] and popular species in many endangered species awareness campaigns. It is easy to say "we are spending a million dollars on protecting a worm?" in Congress, but when more renowned species like a hammerhead shark variety are endangered, they will naturally get more attention. Now scientists can defend their case for funding by pointing to this algorithm.
    • That's interesting, because most americans don't care about preservation.

      My proof?
      Wal-mart (and the associated industries that support low prices).

      Sure, save the whales/sharks/pandas/worms. But I better get my tampico for 0.34$/bottle and jeans for $4.99 so I can afford to help out.
      • whats wrong with low prices? would you prefer high prices so people can't invest in cleaner technology eg. i can't afford that prius because the cost of living means i'm JUST scraping by. i think there is a hole in your thinking there.
    • Re: (Score:3, Insightful)

      by icegreentea ( 974342 )
      People generally don't want to spend their money saving some worm. As it's been suggested before, the focus on megafauna partly exists just because they are charismatic. Panda bears are fricking cute. And people will donate money to save panda bears, their habitat, and everything else living there. It's unfortunate, but it's just facing the reality of the situation. Being able to identity the real keystone species would be great for the actual scientists, conservationists, and policy makers. But when its ti
  • In the context of being an important part of the web, what is the page rank for the species homo sapiens?
    • "Raises", damn-it, "This RAISES the question".

      "Begging the question" is more like circular reasoning - you assume that which you are trying to demonstrate.
  • by sugarmotor ( 621907 ) on Saturday September 05, 2009 @01:34AM (#29321081) Homepage

    The pagerank algorithm is better understood as a kind of Eigenvector Centrality Measure.

    See http://en.wikipedia.org/wiki/Eigenvector_centrality#Eigenvector_centrality [wikipedia.org]

    Meaning it is not new as a method by itself, but applying it to the linking-structure of the WWW in order to produce
    relevant documents for a query, was new. I think it is fair to say that the Google Pagerank matters very little, outside of being able to rank otherwise
      not-comparable search results.

    And so it is better to state that "a specialized Eigenvector Centrality Measure can predict with great accuracy which species are vital to the existence of others" instead of "a modified version of PageRank can predict with great accuracy which species are vital to the existence of others". One can see that also when one realizes that these biologists have no query, no search, no equivalent of search keywords.

    On the other hand, when the post says "Co-author Dr. Stefano Allesina realized he could apply PageRank to the problem when he stumbled across an article in a journal of applied mathematics describing the Google algorithm." -- I guess he might have found the method through the Google name.


  • Awesome, now we know which species we can let go extinct!

  • This could be used to predict which projects are essential to open source and free software.
  • Certainly this is an additional tool that can be used to explore Lovelock's Gaia hypothesis. If other elements were included in the web of interactions such as atmospheric and dissolved CO2, the actions of rocks it might provide a further insight into global warming and what we should be looking at the mitigate it.
  • I am a representative of an important species and if I point to a web page it becomes important?
    How long do I have to point at a certain page to put it on top of Google search results.
  • So what happens when this algorithm determines humans are the least important species to the ecosystem?

"How many teamsters does it take to screw in a light bulb?" "FIFTEEN!! YOU GOT A PROBLEM WITH THAT?"