Please enable JavaScript.

Coggle requires JavaScript to display documents.

Linked - Barabasi (Linked ~ Barabasi (3rd ~ Six Degrees of Separation (Is…

- - - - MafiaBoy - From his bedroom, the teen hacker orchestrated a distributed denial of service attack (DDoS) that was able to crash the websites of some of the biggest names in e-commerce back in the year 2000
      - A reformed persecutor of Christians had a conversion experience and afterward walked nearly 10,000 miles, over twelve years, spreading the message and faith of a man whom he’d never met
      - Both mastered the faster and most effective way to reach the largest number of people, each one in its own time. Neither of them fully grasped the forces that aided them in their actions.
      - Paul and MafiaBoy succeeded because we are all connected
        
        Mapping our interconnectivity
        
        detailed maps of the Internet
        
        companies connected by trade
        
        interactions between specimens and ecosystems
        
        gens working together in a cell
        
        all those diverse maps follow a common blueprint
        
        far-reaching natural laws govern the structure and evolution of all the complex networks that surround us
    - - Reductionism tells us that to comprehend nature, we first must decipher its components, assuming that once we understand the parts it will be easy to understand the whole
      - It is the wrong approach and has resulted in us taking apart the universe and having no idea how to put it back together
      - After spending trillions of research dollars to disassemble nature in the last century, we are just now acknowledging that we have no clue how to continue except to take it apart further, because putting it back together turned out to be harder than scientists thought it would be
      - Complexity
        
        Nature is not a well-designed puzzle with only one way to put it back together and that in complex systems the components can fit in so many different ways that it would take us billions of years to try all the combinations
        
        Nature exploits the laws of self-organization whose roots, he writes, are still largely a mystery
        
        Complexity has a strict architecture. We have come to grasp the importance of networks.
        
        The 'next scientific revolution:
        the science of networks'
  - - - Leonhard Euler in 1736 introduced the idea of graphs and unintentionally created a branch of mathematics known as graph theory, which today is the basis for our thinking about networks
      - "Euler gave birth to graph theory by replacing each of the four land areas with nodes, and each bridge with a link (4 nodes connected by 7 links)"
      - Graphs or networks have properties, hidden in their construction, that limit or enhance our ability to do things with them.
      - The construction and structure of graphs or networks is the key to understanding the complex world around us.
      - Small changes in the topology, affecting only a few of the nodes or links, can open up hidden doors, allowing new possibilities.
      - Until the 1950s, the goal of graph theory was simple: discover and catalogue the properties of the various graphs
    - - Paul Erdos and Alfred Renyi together introduced the 'random network theory model'. Random network theory says that nodes in a network connect to each other randomly and, according to Barabasi, it has dominated scientific thinking about networks since being introduced in 1959
      - Erdos and Renyi never planned to provide a universal theory of network formation. Erdos agreed that networks must have organizing principles that distinguish them from the random network model.
      - What do real networks look like?
  - - - Amazing how Milgram's first paper on the subject occasionally read like an English translation of Karinthy's "Chains"
      - The goal was to find the 'distance' between any two people in the US, sending letters to randomly chosen residents of Wichita and Omaha.
      - Milgram found that the median number o intermediate person was 5.5, amazingly close to Karinthy's suggestion. But Milgram himself never used the phrase "six degress of separation"
    - - Ousa: "Everybody on this planet is separated by only six other people. Six degrees of separation. Between us and everybody else in this planet..."
      - For Guare's Ousa, six degrees applied to the whole world. Thus a myth was born. More people watch movies than read sociology papers.
    - - By inventing the links in 1980, Tim Berners-Lee released a genie, that in less than 10 years turned into the World Wide Web. Largest ever human-made network.
      - Links turn the collection of individual documents into a huge network.. the stitches that keep together the fabric or our modern information society together.
      - Using 'Statistical Mechanics', and focusing on smaller pieces of the web (1k,10k,100k nodes), Barabasi found the separation to be proportional to the logarithm of the number of nodes in the network.
      - NEC group estimated the size of the public indexable web to be around 800 million nodes at the end of 1998. Diameter=18.59(19)
        
        The natural question is why? How do networks achieve such a uniformly short path despite consisting of billions of nodes?
        
        As we add more links, the distance between nodes suddenly collapses, which can be turned into a formula that predicts separation as a function of the number of nodes.
        
        The origin of the small separation is a logarithmic term present in the formula. The logarithm shrinks the huge networks.
        
        "Small worlds" are a generic property of networks in general. There is a new geometry to master in order to make sense of the complex world around us.
        
        Our society with 6 billion nodes has a separation of 6, the web with close to a billion nodes has a separation of 19, the internet, with thousand of routers has a separation of 10
    - - Erdos, also in Budapest, was 17 yrs old
      - Alfred Renyi, was 9 yrs old, was good friends with Karinthy's son, Ferenc.
      - Erdos and Renyi in 1959 wrote their famous string of papers on random networks.
        
        Stanley Milgram is a child of Hungarian father and Romanian mother who came to the US and settled in the Bronx
  - - - Granovetter proposed that when it comes to finding a job, getting news, launching a restaurant, or spreading the latest fad, our weak social ties are more important that our strong friendships
        
        Interviews: 'Was it a friend? Or just an acquaintance?
      - An image of a society that is very different from the random universe Erdos and Renyi depicted
        
        a fragmented web of fully connected clusters communicating through weak ties seems truer than the randon picture
      - Society is structured into: 1) Highly connected clusters; 2) Close-knit circle of friends
    - - To keep track of their distance from Erdos ~ number "0" - Those who co-autored a paper with him, "1", those who wrote with a co-autor, "2", and so on..
      - The web of science is a small scale prototype of our social network, its links are regularly published.
    - - Tamás Vicsek - dpt of biological physics - Budapest - linked all mathematicians through papers published between 1991 and 1998
      - Mark Newman - physicist - Santa Fe Institute (US) - investigates the collaboration graph of scientists - physicists, doctors, computer scientists
      - The works, combined, offered evidence that 'Clustering is indeed present in social systems
      - Watts and Strogatz: "clustering does not stop at the boundaries of the network" - a realistic model of society must allow for distant links
        
        Surprise: even a few extra links are sufficient to drastically decrease the average separation
        
        Huge networks don't need to be full of random links to display small world features. A few such links will do the job.
  - - - Média de 21 conhecidos, mas scores vão de 2 a 95
      - Algumas pessoas são mais articuladas: they are Connectors
        
        Componente importante das redes sociais, propriedade funtamental da maioria das redes
        
        Conectam diferentes raças, níveis de educação, e status social
        
        Nodes with an anomalously large number of links
        
        'Descoberta' dos conectores muda tudo: derruba os outros dois modelos (Erdós-Rényi e Watts-Strogatz), e resulta no abandono definitivo da visão randômica.
    - - Cyberspace embodies the ultimate freedom of speech..
      - .. but, if you post information on the Web, will anybody notice it?
      - most intriguing result of Web-mapping project: complete absence of democracy, fairness and egalitarian values on the Web.
        
        University of Notre Dame webserver: 90% of documents have 10 or fewer links pointing to them - while a few, about three, are referenced by close to a million other pages.
        
        The hubs are the strongest argument against the utopian vision of an egalitarian cyberspace.
      - On the Web, the measure of visibility is the number of links
    - - Observation that every actor in Hollywood could be connected to Kevin Bacon with typically two to three links
      - Two computer science students, Glen Wasson and Brett Tjaden, from University of Virginia, connected the IMDb.com, database of actors and movies
      - A random universe does not support connectors
        
        On the Web, a few hubs grab most of the links
        
        Hubs play a crucial role in guaranteeing the Internet robustness against failures
        
        Hubs are ubiquitous, a generic building block of our complex interconnected world
        
        Hubs force us to reconsider our knowledge of networks, and to ask 3 fundamental questions:
        
        How do hubs appear?
        
        How many of them are expected in a given network?
        
        Why did all previous models fail to account for them?
        
        Hubs follow strict mathematical laws
      - the list of actors with the most movies fails to give the us the most-connected actors ~ Cartoon voices and Porn Stars
        
        John Carradine tem 4000 links para outros atores - Robert Mitchum atuou com 2905 colegas - ao remover qualquer um destes 'Hubs de Hollywood', o caminho de praticamente qualquer ator para Kevin Bacon irá se tornar drasticamente maior.
        
        central position in networks is reserved for those nodes that are simultaneously part of many large clusters
        
        Kevin Bacon - 2.79 avg distance - 876th / Rob Steiger - 2.53 avg distance - 1st / Donald Pleasence - 2.54 avg distance - 2nd / Martin Sheen, Christopher Lee, Robert Mitchum, Charlton Heston - 2.57 avg
  - - - Pareto Law or Principle - the 80 / 20 Rule
      - In most cases, four-fifths or our efforts are largely irrelevant
      - All systems following Pareto's Law share a 'property'
    - - When our little robot started to map the Web, we found many nodes with a few links only, and a few hubs with an extraordinarily large number of links.
        
        The distribution of links on Webpages follows a mathematical expression called a POWER LAW.
        
        Power Law histogram is a continuously decreasing curve, implying that many small events coexist with a few large events.
        
        Each Power Law is characterized by a unique exponent - the degree exponent.
        
        Power Laws formulate in mathematical terms the notion that a few large events carry most of the action.
      - Most quantities in nature follow a BELL CURVE
        
        A distribution mode similar to the peaked distribution of random networks.
      - Hubs force us to reconsider our knowledge of networks, and to ask 3 fundamental questions:
        
        How do hubs appear? [What was it about the Web that prompted it to defy the strict predictions of random networks?]
        
        How many of them are expected in a given network?
        
        Why did all previous models fail to account for them?
        
        Hubs follow strict mathematical laws -> POWER LAW
    - - The discovery of power laws in the Web forced us to acknowledge the hubs
      - Neither hierarchy of omnipresent hubs nor the accompanying Power Laws were accounted for in network theories in 1999.
      - Each scale-free network will have several large hubs that will fundamentally define the network's topology.
      - In a continuous hierarchy there is no single node characteristic of all the nodes - the Power Law forces us to abandon the idea of scale.
      - The finding that most important networks (WWW, cell) are scale-free provided legitimacy to hubs.
        
        Hubs determine the structural stability, dynamic behavior, robustness, and error and attack tolerance of real networks.
        
        Complex networks started to speak to us in a language that scientists trained in self-organization and complexity could finally understand. They spoke of order and emerging behavior.
        
        "There were laws behind complex networks"
    - - Why do liquids, magnets, and superconductors lose their identity at some critical point and decide to follow identical power laws?
        
        Renormalization: in the vicinity of the critical point, the laws of physics applied in an identical manner at all scales, from single atoms to boxes with millions of identical atoms acting in unison.
        
        We finally learned that when giving birth to order, complex systems divest themselves of their unique features, and display a universal behavior that has similar characteristics in a wide range of systems.
        
        Are real networks in a continuous state of transitions from disorder to order?
        
        Why do hubs appear in networks of all kinds, ranging from actors to the Web?
        
        Why are they described by power laws?
        
        Are there fundamental laws forcing different networks to take up the same universal form and shape?
        
        How does nature spin its webs?
  - - - Gathering data from known netwoks
        
        Power grid of the Western United States
        
        C. elegans topology
        
        Hollywood Actor Database
        
        The wiring diagram of a computer chip by IBM
        
        In almost all systems (IBM, actors, power grid) the distribution follows a Power Law
        
        An Insight: Rich-get-Richer phenomenom
      - Most real networks share an essential feature: GROWTH
        
        growth forces us to rethink our modeling assumptions - networks are not random, not static
        
        It's easy to model a growing network
        
        Model A - We start adding nodes, one after another, and each node has two links.. our 3rd node will link to both of them, the 4th has 3 to chose.
        
        Model A differs from Erdós and Rényi random network model in its growing nature.
        
        Despite the fact of choosing links randomly and democratically, nodes in Model A are not equivalent with each other.
        
        There is a clear advantage for the senior nodes.
        
        The poorest node will be the last one to join the system.
        
        Growth: For each given period of time we add a new node to the network: one node at a time.
      - The webpages we link to are not ordinary ones - they are HUBS: PREFERENTIAL ATTACHMENT
        
        UNDEMOCRATIC: Hollywood & the WWW force us to abandon the second important inherent assumption inherent in random networks: their democratic character.
        
        Preferential Attachment: We assume that each new node connects to the existing nodes with two links. Given the choice between 2 nodes, one with twice as many links as the other, it is twice as likely that the new node will connect to the more connected node.
        
        As the 1st model to explain the scale-free power laws seen in real networks, it quickly became known as the scale-free model.
        
        Seniority, however, is not sufficient to explain power laws.
        
        Hubs require the help of the second law, preferential attachment
        
        Preferential Attachment induces a rich-get-richer phenomenon
        
        How do latecomers make it in a world in which only the rich get richer?
      - Could either growth or preferential attachment alone explain the power laws?
        
        The evolution of real networks is far more complex than the scale-free model predicts.
        
        Internal Links: new links emerge spontaneously inside the network, not only when new nodes join it.
        
        Many nodes and links can disappear.
        
        Aging: nodes stop acquiring links after retirement.
        
        Linking to a node would not be simply proportional to the number of links the node has, but would follow some more complicated function.
        
        BUT, in most cases, when GROWTH and PREFERENTIAL ATTACHMENT are simultaneously present, HUBS and POWER LAWS emerge as well.
        
        The scale-free model embodies a new modeling philosophy, by viewing networks as dynamical systems that change continuously over time.
        
        Goals have shifted from describing the topology to understanding the mechanisms that shape network evolution.
        
        Static vs Growing
        
        Random vs Scale-Free
        
        Structure vs Evolution
        
        No matter how large and complex a network becomes, as long as preferential attachment and growth are present, it will maintain its hub-dominated scale-free topology.
- - - - In random networks, removing only a few nodes will have little impact, but if the nº of removed nodes reaches a critical point, the system abruptly breaks into tiny unconnected islands.
      - 2000: Motivated by the DARPA proposal, we performed a series of computer experiments to test the Internet's resilience to routers failures.
        
        We could remove as many as 80% of all nodes, and the remaining 20% still hung together, forming a tightly interlinked cluster.
        
        When we no longer selected the nodes randomly, but attacked the network by targeting the hubs, the consequences were evident.
        
        The removal of a few hubs broke the Internet into tiny, hopelessly isolated pieces.
        
        Havlin and Duncan Watts: demonstrated that, when the largest nodes are removed, there is a critical point beyond which the network breaks apart.
        
        Therefore, hidden within their structure, scale-free networks harbor an unsuspected Achilles' Heel, coupling a robustness against failures with vulnerability to attack.
        
        What is the source of this amazing topological robustness?
        
        The structural unevenness of scale-free networks: failures disproportionately affect small nodes
        
        Do all scale-free networks display the same degree of error tolerance?
        
        Shlomo Havlin, expert on percolation theory, set out to calculate the fraction of nodes that must be removed from an arbitrarily chosen network, random or scale-free
        
        They found that for scale-free networks the critical threshold disappears in cases where the degree exponent is smaller or equal to 3.
        
        Amazingly most networks of interesst, from the Internet to the cell, are scale-free and have a degree exponent smaller than 3. Therefore, they never break.
- - - - Internet researchers are increasingly morphing from designers into explorers, like biologists or ecologists faced with an incredibly complex system that exists independently of them.
      - The Internet is comprised of physical lines and routers. It is all hardware. How could it follow the same rules that humans do when establishing their weightless social links or adding URLs to their Webpage?
    - - No central authority has controlled or documented its grouwth and design.
      - What neither computer scientists nor biologists know is how the large-scale structure emerges once we put the pieces together.
      - 1999: The Faloutsos Brothers find the connectivity distribution of the Internet routers follows a power law
        
        The discovery meant that all tools used to model the structure of the Internet before 1999, based on ideas rooted in random networks, were simply wrong.
  - - - When an institution decides to link its computers to the Internet, the parameter is cost of communication.
      - Regarding the bandwidth, the closest node is often not the best choice.
      - Routers offering more bandwidth likely have more links as well.
      - When chosing a good place to link, we will gravitate toward the more heavily connected access points -- a source of preferential attachment.
        
        Nodes rich in links acquire more links than nodes with a few links only.
    - - Growth
      - Preferential Attachment
      - Distance Dependence
      - Underlying Fractal Structure
      - Each of these forces alone, if taken to the extreme, could destroy the scale-free topology.
        
        This very balance of power is the Internet's own Achilles' heel.
    - - There will be soon over 3 billion Internet-connected cell phones and close to 16 billion Internet-connected computers embedded in everything from toasters to fashion designs.
- - - - The process that separates winners the winners from the losers: competition in complex systems, where each node has a certain FITNESS.
        
        FITNESS is a quantitative measure of a node's ability to stay in front of the competition.
        
        May have genetic roots in people
        
        May be related to product and management quality for companies
        
        Talent for actors
        
        Content for Websites
        
        Your ability to make friends relative to everybody in your neighborhood
        
        A company's competence in luring and keeping consumers
        
        The introduction of FITNESS changes what is considered attractive in a competitive environment
        
        Preferential attachment is driven by the product of the node's fitness and the number of links it has.
        
        If two nodes have the same fitness, however, the older one still has an advantage.
        
        The simple fitness model was 'our' 1st attempt to account for Google
        
        "Our quick fix opened an unexpected window to a rich family of phenomena, that are invisible in a fitness-free universe.
  - - - Would the power laws be present in such a competitive environment - would they apply to the fitness model?
      - Would networks driven by competition continue to be scale-free?
      - Would the fierce competition for links destroy the signature of order that we had uncovered?
    - - In 1900, Planck was the 1st to introduce the assumption that light and heat are emitted in small packages, or discrete quanta.
      - In 1922 Einstein predicted the photoelectric effect, assuming that light is indeed made of tiny particles, called photons.
      - In 1924 Bose sent Einstein a letter arguing that our ability to distinguish certain subatomic particles is an illusion borrowed from daily life.
        
        Bose showed that once statistical mechanics and thermodynamics are modified to incorporate the fact that certain subatomic particles are truly identical.
        
        Six months later Einstein published the 'Second Treatise' predicting a very strange phenomenon, the Bose-Einstein condensation.
        
        When particles reach a state where atoms can be forced into their lowest energy state, they form a new form of matter.
        
        The discovery started a revolution in atomic physics, helping to understand phenomena as star formation and supercondutivity.
        
        How the Bose-Einstein condensation helps us to understand the behavior of the fitness model?
        
        Bianconi substituted fitness for energy, assigning an individual energy level to each node in the fitness model.
        
        Suddenly the calculations started to resemble those that Einstein ran across eighty years earlier when he discovered the condensate.
        
        There was a precise mathematical mapping between the fitness model and a Bose gas: each node relates to an energy level in the gas.
        
        The larger the node's fitness, the smaller its corresponding energy level.
        
        Adding a new node to the network is like adding a new energy level to the Bose gas.
        
        In this mapping, complex networks are like a huge quantum gas, their links behaving like subatomic particles.
        
        Just as in a Bose-Eistein condensate, in some networks the fittest node could theoretically grab all the links - The Winner Takes All.
    - - In most networks, despite the fierce competition for links, the scale-free topology survives - a fit-get-rich behavior.
      - In the 2nd category, the winner takes all, leaving very little for the rest of the nodes.
      - Google's rapid rise is not an indication of winner-takes-all behavior - it only tells that the fit get rich
        
        When the winner takes all, there is no room for a potential challenger.
        
        There is a network aht carries the signature of a Bose-Einstein condensate: Microsoft
        
        Is the Facebook Monopoly a case that puts the Web as a winner takes all category?
- - - - 250 partners a year ~ 2.500 sexual contacts
      - Many of the earliest cases were linked to him.
      - What is the topology of the sexual network that carries AIDS?
        
        In 1996 Swedish scientists conducted interviews with 4.781 individuals, obtained the nº of links for 2.810 nodes in the Swedish sex web.
        
        The distribution followed a power law, and taken together, the data offered striking evidence that the network has a scale-free topology.
        
        The scale-free topology implies that, though most people have only a few sexual links, the web o sexual contacts is held together by a hierarchy of highly connected HUBS.
        
        In the light of these results, the Trieste predictions offer a new perspective on the AIDS epidemic:
        
        The unique role of HUBS suggests a bold cruel solution: as long as resources are finite we should treat only the hubs.
        
        As we don't know who the hubs are, there are methods for identifying high-risk groups, and individuals most likely to be the source of the epidemic.
        
        Policies that continued to distribute treatment randomly, continued to have zero threshold and failed to stop the virus.
        
        Any policy that displayed bias toward the more connected nodes, even a small bias, restored the finite epidemic threshold, lowering the rate at which the disease spreads.
    - - A few decades ago it was impossible to gain worldwide fame literally overnight, even in America.
    - - May 8, 2000 - Love Bug, the most damaging computer virus ever.
        
        What is amazing about the Lov Bug is that despite the widel and freely available antidote, the virus still exists
        
        Trieste (2000): Pastor-Satorras and Alessandro Vepignani showed that in contrast to solid predictions of threshold models, in real networks high virulence does not guarantee a virus's spread.
        
        Steve White (IBM) paper argued that biologically inspired epidemic models do not properly describe the spread of Love Bug and other computer viruses.
        
        In that very week, Achilles' Heel paper was featured on the cover of Nature, saying that on the Internet, underlying network has a scale-free topology.
        
        In scale-free networks the epidemic threshold vanishes. Even if a virus is not very contagious, it spreads and persists.
        
        Highly linked HUBS offer a unique means by which viruses persists and spread.
        
        The Internet helped us discover scale-free networks in the first place.
  - - - It's a bell curve
    - - Elihu Katz (1954): Study the effect of social ties on behavior ~ how physicians adopt a new drug
        
        Asked to list 3 doctors with whom they most often discussed medical practices.
        
        The lists allowed to reconstruct the complex network of social ties and influence.
        
        A few were named by a large fraction of their colleagues ~ the hubs.
        
        Early adopters and early majority were doctors with numerous social links.
        
        HUBS, the integral components of scale-free networks, are the statistically rare, highly connected individuals who keep social networks together.
        
        Opinion Leaders
        
        Power Users
        
        Influencers
        
        Sociologists and marketing experts treated hubs as unique phenomena.
        
        Aiming to explain the disappearance or spread of viruses and fads, it was created a very useful tool called 'threshold model'.
        
        The likelihood that each innovation will be adopted is its 'spreading rate'.
        
        To define the fate of an innovation we must calculate the 'critical threshold', which is determined by the properties of the network in which it spreads.
        
        If the spreading rate of the innovation is less than the critical threshold, it will die out shortly.
        
        If the spreading rate is over the critical threshold, it will increase exponentially until everybody who could use it does.
        
        The framework offered by scale-free networks provided the legitimacy hubs deserve.