Summary |
要 約 |
>Top 0. Introduction:
- Message of Paul:
- He did not wander randomly; he reached out to the biggest communities
of his era, to the people and place in which the faith could germinate
and spread most effectively. He was the first and by far the most
effective salesperson of Christianity.
- 2,000 years after Paul, we now know that he answer lied as much
in the structure and topology of the network.
- Jorge Luis Borges,"Everything touches everything."
- Recent scientists have been learning to map our interconnectivility
- We have taken apart the universe and have no idea how to put it
back together. Reductionism was the driving force behind much of 20C's
scientific research.
- Divide and conquer; the devil is in the details.
- Nothing happens in isolation. Most events and phenomena are connected,
caused by, and interacting with others.
|
0. 序文：
- 使徒パウロの神託：
- 彼はランダムに徘徊したのではなかった。当時の大きな共同体を対象に、信仰が最も効果的に伝導できる人々と場所に到達した。彼はキリスト教販売の最初にして最も効率の良いセールスマンであった。
- パウロの後二千年を経て、我々はネットワークの構造とトポロジーの中に潜む解答を知った。
- Jorge Luis Borges曰く、"すべてがすべてに接している。"
- 最近の科学者は相互接続性をマップ化することを学んでいる。
- 我々は今まで宇宙を分解して理解してきたが、それを元へ戻すすべを知らない。還元主義は20世紀の科学研究のほとんどの分野での原動力であった。
- 孤立していては何事も起こらない。ほとんどの出来事と現象は何かとつながってしており、原因があり、他と相互作用がある。
|
>Top
1. The random universe:
- 1736 Leonard Euler:
Graph theory is the basis for our thinking about network; "nodes"
and "links"
- Konigsberg bridge problem: Nodes with an odd number of links
must be either the starting or the end point of the journey. Thus,
such a path cannot exit on a graph that has more than two nodes
with an odd number of links.
- Graphs or networks have properties, hidden in their construction,
that limit or enhance our ability to do things with them.
- Society, the Internet, a cell, or the brain can all be represented
by graphs, each is clearly very different from the others.
- Random graph theory: "God enjoys playing dice"
- A. Einstein said, "God does not play dice with the
universe.
- A party for 100 guests:
- Organize a party for a 100 guest who have been selected and
invited because they do not know a single other person on the
guest list.
- Soon you will see 30 to 40 groups of two or three.
- There are invisible social links between people who met earlier
but now belong to different groups.
- As a consequence, subtle paths start connecting people who are
still strangers to each other.
- It would take only 30 minutes to form a single invisible social
web that includes all guests in the room.
- >Top Random network theory (Erdos
and Renyi, 1959):
- One is the threshold: one acquaintance per person, one
link to at least one other neuron for each neuron in the brain.
- As the average number of links per node increases beyond the
critical one, the number of nodes left out the giant cluster decreases
exponentially.
- If the network is large, despite the links' completely random
placement, almost all nodes will have approximately the same number
of links. (Poisson distribution)
- Mathematicians call this phenomenon the emergence of a giant
component, one that includes a large fraction of all nodes.
Physicists call it percolation and we just witness a phase
transition, similar to the moment in which water freezes.
- Chance and randomness are very much a part of their lives.
|
1. ランダムな宇宙:
- 1736年 L. オイラー:
グラフ理論、特に"ノード(節点)"と"連結"は我々がネットワークを考える際の基礎となる。
- ケーニヒスブルグの橋問題（一筆書き): 奇数点をもつノードはそのルートの始点または終点でなければならず、従って奇数の端点を３つ以上もつグラフは一筆書きのパスは存在しない。
- グラフやネットワークにはその構造の中に潜む特徴があり、それはネットワークに対応する際に我々の能力を制限したり高めたりする。
- 社会、インターネット、細胞、大脳、これらは皆グラフによって表現でき、各々が非常に異なる特徴を備えている。
- ランダム・グラフ理論：「神はサイコロ遊びを好む」
- アインシュタイン曰く、「神は宇宙に関してサイコロ遊びをしない。
- 100人のパーティ:
- 初対面の100人を選びパーティーを企画する。
- パーティー開始後30-40分で、30-40人のグループが2、3つできる。
- 異なるグループに属しているが、以前面識のある人達の間で見えない社会的なリンクがある。
- その結果、互いに見知らぬ人たちの間をつなぐ微妙なパスが張られる。
- およそ30分ほど経つと、見えざる社会的なWebが形成され、すべての部屋中のゲストを含むようになる。
- ランダム・ネットワーク理論:
(Erdos and Renyi, 1959)：
- １つが閾値である。即ち、知人が一人いる状態。大脳では一つのニューロンは他のニューロンとまず１つのリンクを張る。
- ノード当たりの平均のリンク数は限界値を超えて増加すると、大きな集団からはずれるノードの数は指数関数的に減少する。
- リンクを完璧にランダムに行うとしても、ネットワークが大きければ、ほとんどすべてのノードはほぼ同じ数のリンクをもつようになる。(ポアソン分布)
- 数学者はこの現象を、大成分、即ちすべてのノードの最大グループの出現と呼ぶ。物理学者はこれを濾過作用とよび、水が凍るときのような相転換が起こるという。
- チャンスとランダムネスとはコインの表裏である。
|
>Top 2. Six degrees of
separation:
- Distance between any two people;
by Stanley Milgram, 1967;
- found that "distance" between any two people in US.
The question driving the experiment was, how many acquaintance would
it take to connect two randomly selected individuals? Milgram himself
pointed out: "I asked a person of intelligence; he said that
it would require 100 intermediate persons."
- His experiment entailed sending letters to randomly chosen, which
contained following message.:
- Add your name to the roster at the bottom.
- Detach one postcard. Fill it out and return it to Harvard
Univ.
- If you know the target person on a personal basis, mail this
folder directly to him (her).
- If you do not know the target person on a personal basis,
do not try to contact him directly. Instead, mail this folder
to a personal acquaintance who is more likely than you to know
the target person.
- >Top He found that the median number of intermediate person was 5.5.
Round it up to 6, and you get the famous "six degrees of separation."
- How every person is a new door opening up into other worlds.
- Web's degree of separation:
- Robot or crawler: The big search engines have thousands of computers
running numerous robots that constantly look for new documents on
the Web.
- The measurements indicated that Webpages were on average 11
clicks away from each other.
- First, we took a small portion of the Web, with only 1000 nodes.
Next, we took a slightly larger piece with 10,000 nodes, and determined
the separation again. We repeated this for the largest system, and
looked for trends in the obtained node-to-node distances. This finding
allowed us to predict the separation on the full Web as long as
we know the total number of documents out there. Thus our expression
predicted that the diameter of the Web was 18.59, close to 19.
(19 degrees of separation)
- Small separations are common in just about every network, e.g.:
- species in food web: 2 links
- molecules in the cell are separated on average by 3 chemical
reactions
- scientists in different fields of science are separated by
4 - 6 coauthership links
- neurons in the brain are separated by 14 synapses.
- Consider a network in which the nodes have on average k links.
This means that form a typical node we can reach k other nodes
with one step. There are$k^2$ nodes two links away and roughly $k^d$nodes exactly d links away. Therefore, if k is large, for even small values of d the number of nodes you
can reach can become very large.
|
2. ６段階の分離：
- 任意の２人の距離:
Stanley Milgram (1967):
- 米国での２人の間の「距離」について考察した。この実験をするに当たっての疑問は、任意に選んだ２人の個人をつなぐためには一体何人の知人が必要かというものでした。Milgram自身曰く「学識者に聞いたところ、100人の仲介人がいるだろう。」とのこと。
- 彼の実験は任意に抽出された人に対し以下内容の手紙を出すことになった。
- 下記の部分の名簿に名前を追加して下さい。
- 葉書に記載して、ハーバード大学宛に別途送付して下さい。
- 目標人物を個人的に知っている場合には、このフォルダーを直接、彼 (彼女)に送付して下さい。
- 目標人物を個人的には知らない場合、その相手と直接連絡をとるようなことはせずに、このフォルダを、その目標人物のことをあなたよりよく知っていそうな知人に送付して下さい。
- 実験結果は、仲介人の数は中位数は5.5であった。これを丸めて６とし、有名な"６段階の分離"を得ることができる。
- これは誰もが、他の世界に対してドアが開かれていることを示す。
- Webでの分離の程度：
- 検索エンジン、検索ロボット：
大きな検索エンジンは、何千というコンピュータを使い数多くのロボットを走らせWebに掲載された新情報を検索している。
- 測定によればWebページは相互には平均11クリック離れている。
- まず、1000ノード程度のWebの小さな部分をとる。次に10,000ノードのやや大きな部分をとり、再度分離の程度を調べる。これを大きなシステムに関しても繰り返し、ノード間の距離の傾向を探る。この結果、すべての文書がある十分大きなWebの分離状況を予測することができる。こうれして我々はWeb全体の分離の程度、いわば直径が18.59、ほぼ19であることが予想された。(19段階の分離)
- ほとんどのネットワークではもっと小さな分離が普通である。例えば
- 食物連鎖：２リンク
- 細胞中の分子は３つの化学反応で分離
- 異分野の科学者は4-6人の共著者で分離
- 大脳中のニューロンは14シナプスで分離
- ノードが平均 k リンクをもっているネットワークを考える。これはあるノードから k 個の他のノードにワンステップで行けることを意味する。即ち$k^2$ 個のノードは２リンク離れており、ほぼ $k^d$ 個のノードは d リンク離れていることになる。
このことは、k が大きければ、ノードの d がたとえ小さな数字であっても、非常に大きな数となることを示している。
|
>Top 3. Small Worlds:
 Strength
of Weak Ties:
Our close friends are often friends with each other as well, fully
connected circles by strong ties shown as black lines. Weak ties,
shown as green lines, connect the members of these friendship circles
to their acquaintances. Weak ties play an important role in any number
of social activities, from spreading rumors to getting a job.
- Weak ties play a crucial role: in our ability to communicate
with the outside world. To get new information, we have to activate
our weak ties. The weak ties, or acquaintances, are our bridge
to the outside world, since by frequenting different places they
obtain their information from different sources than our immediate
friends.
- Clustering coefficient:
tells how closely knit your circle of friends is.
- If it is 10 means that all your friends are good friends with
each other.
- If it is 0 means that your are the only person who holds your
friends together, as they do not seem to enjoy each other's company.
- >Top Erdos number:
Paul Erdos published over 1,500 papers with 507 coauthors. To keep
track of their distance from Erdos, mathematicians introduced the
Erdos number. Erdos has Erdos number zero. Those who coauthored a
paper with him have Erdos number one. Those who wrote a paper with
an Erdos coauthor have Erdos number two, and so on. The scientific
community forms a highly interconnected network in which all scientists
are linked to each other through the papers they have written.
- <Figure left>
People live on a circle along which everybody knows their immediate
neighbors. In this simple model each node has exactly 4 neighbors,
who are connected to each other by 3 links. If all 4 neighbors
were connected to each other, there would be 6 links between
them. Since there are only 3, the clustering coefficient is 3/6 =
0.5
 - Each node (red dot) is connected to its immediate
and next-nearest neighbors (left). To make this world a small one,
a few extra links were added, connecting randomly selected nodes (right).
These long-range links (blue lines) offer the crucial shot-cuts between
distant nodes, drastically shortening the average separation between
all nodes.
|
3. 小さな世界:
- <左図> 弱い連結の強さ:
親しい友人はしばしば互いに友人関係でもあり、黒線のように強い連結で結ばれている。弱い連結は、緑線で示したように、これらの友情の和を彼らの知人とをつないでいる。弱い連結は様々な社会活動、噂から仕事探しに至るまで重要な役割を演じる。
- 弱い連結は外の世界と通信ができる上で決定的な役割を演じる。新たな情報を得るために、我々は弱い連結を活性化する必要がある。弱い連結、即ち知り合いは、外の世界への架け橋である。それは異なる場所へ頻繁に出かけ、親しい友人とは異なる情報源からの情報を得るからである。
- 集団係数:
- もし10の場合、すべてのあなたの友人は互いに親友関係。
- もし0の場合、あなたの友人を結びつけるのはあなただけで、彼らは互いに交際することを楽しんでいるように見えない。
- Erdos数:
Paul Erdosは 507名の共著者と共に1,500の論文を出版した。Erdosからの距離を把握するために、数学者はErdos数の概念を提案した。Erdos自身のErdos数は 0である。Erdosの共著者のErdos数は 1である。Erdosの共著者と一緒に論文を書いた人達はErdos数 2というようにする。科学者は、すべての科学者が互いに論文共著を通じて極めて緊密なコミュニティを形成している。
- <図左側>
円に沿って人々が住んでおり、だれもがその両隣だけ知っているとする。このモデルでは、各ノードは 3段階のリンクで相互接続された 4つの隣人から成る。もしすべての４つの隣人が相互接続されていれば、その間には 6つのリンクとなる。従って 3つのリンクしかなければ、その集団係数は3/6
= 0.5となる。
- <左図>各ノード(赤点)は一つおきに他のノードと接続している。この世界を若干の追加のリンクをランダムに選んだノードとの間に貼る。この長いリンク(青線)によって遠方のノードのショートカットが得られ、その結果すべてのノード間の平均分離の状況を劇的に短縮できる。
|
>Top 4. Hubs and
Connectors:
- A simple test to measure how social you are:
Here is a lit of 248 surnamed compiled from a phone book and you are
asked if you know anybody with that name. If you know three people
named Jones, you get 3 points.
- In the collage class; the scores ranged 2 - 95.
- In a random sample; ranged 9 - 118.
- In a highly homogeneous group: ranged 16 -108
- Conclusion: A handful of people with a truly extraordinary knack
of making friends and acquaintances. They are connectors.
- >Top Connectors:
Connectors are an extremely important component of our social network.
They create trends and fashions, make important deals, spread fads,
or help launch a restaurant.
- Connectors - nodes with an anormalously large number of links
- are present in very diverse complex systems, ranging from the
economy to the cell.
|
4. ハブとコネクタ:
- 社交性を測る簡単なテスト:
ここに電話帳から取った248名の氏名のリストがある。この中で同じ姓名をもつ知人が何人いるだろうか＞もしJonesという姓名をもつ知人が３人いれば、３点とする。
- 大学のクラス：得点分布は2 -95点
- ランダムサンプル：9 -118点
- 同一性の高いグループ：16 - 108点
- 結論：ほんの一握りの人々が異常なほど友人・知人を作るのに長けている。彼らはコネクターなのである。
- コネクター:
コネクターは社会ネットワークの中で非常に重要な要素である。彼らは流行やファッションを創造し、重要な取引を成立させ、噂を広め、レストラン開業を手伝う。
- コネクターは、異常なほどの多くのリンクを張るノードであって、経済社会から細胞に至るまで、多様で複雑なシステムの中に存在している。
|
>Top 5. The 80/20
Rule:
- Vilfredo Pareto in the early 1900s:
Pareto's Law: known as the 80/20 rule; E.g..
- 80% of profits are produced by only 20% of the employee.
- 80% of customer service problems are created by only 20% of
customers.
- 80% of decisions are made during 20% of meeting time.
- >Top Power law:
The network our robot brought back from its journey had many nodes
with a few links only, and a few hubs with an extraordinarily large
number of links. The distribution of links on various Webpage precisely
follows a power law.
- Quantities in nature (ranging from our IQs to the velocity of
molecules in a gas) follow a bell curve; a distribution characterizing
random networks.
- The distinguishing feature of a power law is not only that there
are many small events but that the numerous tiny events coexist
with a few very large ones. These extraordinarily large events
are simply forbidden in a bell curve.
- US highway:
Cities are the nodes and the highways connecting them the links.
This is a fairly uniform network. Such uniformity is an inherent
property of random networks with a peaked degree distribution.
- US airline route:
A few hubs from which flights depart to almost all other US airports.
The vast majority of airports are tiny, appearing as nodes with
at most a few links connecting them to one or several hubs.
- >Top <Bell Curve>
Most nodes have the same number of links and no highly connected nodes.
- <Power Law distribution>
Very many nodes with only a few links, while a few hubs with large
number of links.
- Distinguishing feature of a power law is not only that there
are many small events but that the numerous tiny events coexist
with a few very large ones.
- Critical point:
Near critical point, elements of order and disorder mix within the
same material. In the vicinity of the critical point several key quantities
follow power laws.
- Correlation length:
The distance over which atoms communicate with each other, the
correlation length, is often used as a rough measure of the cluster
size.
- Critical exponent:
As we approach the critical point this correlation length increases
following a power law characterized by a unique critical exponent.
- Leo Kandanoff:
In the vicinity of the critical point, atoms should be considered
communities that act in union. Atoms must be replaced by boxes of
atoms such that within each box all atoms behave as one.
- Why power laws appears each time order spontaneously emerged
in complex systems.
|
5. 80/20の法則:
- Vilfredo Paretoは1900年代初期に、80/20の法則として知られるパレートの法則を発見した。
例えば
- 80%の利益は、20%の従業員によって生み出されている。
- 80%の顧客サービスの問題は、20%の顧客によって生じている。
- 80%の意思決定は、20%の面談時間内に決まる。
- べき乗則:
ロボットによってインターネットの結びつきを調査した結果、多くのノードはいくつかのリンクしかなく、少数のハブが異常に多数とリンクを張っていることが判明した。様々なWebページのリンクの分布は、正確にべき乗則になっている。
- 自然界の多くの数量分布 (IQ分布やガス分子の速度分布のように) と同じく、ランダムなネットワークの特徴である正規分布の釣鐘曲線になる。
- べき乗則の特徴は、多くの小さな事象があるということだけでなく、数多くの小さな事象が少数の非常の大きな事象と共存していることである。これら異常に大きな事象は、正規分布では存在しない。
- 米国ハイウェイ:
都市はノードで、それをつなぐハイウェイはリンクである。これは概して一様なネットワークである。この一様性はピーク分布のあるランダムネットワークの固有の性質である。
- 米国航空ルート:
少数のハブ空港があり、そのを発進し全米のほとんどの飛行場へ行くことができる。圧倒的多数の飛行場は小規模なノードであって、それらは一つまたは少数のハブとつながっている。
- ＜左図＞ 釣鐘曲線分布:
多くのノードは同じリンクを持ち、極端な多数をつなぐノードはない。
- ＜べき乗則分布＞
ほとんど多くのノードが少数とリンクしており、少数のハブだけが非常に多数のリンクをもつ。
- べき乗則の際だった特徴は数多くの小さな事象だけでなく、その小さな事象が少数の非常に大きな事象と共存していることにある。
- 臨界点：
臨界点は、秩序と無秩序の要素が同じ物質中で混ざっている状態である。臨界点の近くでは、いくつかの主要量はべき乗則に従う。
- 相関距離：
原子が相互に通信し合う距離をいい、しばしば群の大きさの概数となる。
- 臨界指数：
臨界点に近づくと、この相関距離は増加し、固有な臨界指数によって特徴づけられるべき乗則に従うようになる。
- Leo Kandanoff:
臨界点の近くでは、原子はコミュニティを作って統一行動をとるように見える。原子は、原子の詰まった箱によって置き換えられる。各箱の中のすべての原子は一つのように振る舞う。
- 複雑系の中で自然発生的に秩序が発生するとき、なぜべき乗則が現れるのか？
|
>Top 6. Rich get
richer:
- Let us assume that each new node has two links. Thus, our third
node will link to both of them. The fourth node has three nodes from
which to choose. We can continue this process indefinitely, so that
each time we add a new node, we connect it to two randomly selected
nodes. The network generated by this simple algorithm, called Model
A, differs from the random network.
- The first nodes in Model A will be the richest, since these
nodes have had the longest time to collect links. The poorest
node will be the last one to join the system, with two links only.
- In real networks linking is never random. Instead, popularity
is attractive. Webpages with more links are more likely to be
linked to again, highly connected actors are more often considered
for new roles, highly cited papers are more likely to be cited
again, connectors make more new friends.
- Starting from two connected nodes (top left),
in each panel a new node (red dot) is added to the network. When deciding
where to link, new nodes prefer to attach to the more connected nodes.
Thanks to growth and preferential attachment, a few highly connected
hubs emerge.
- Could either growth or preferential attachment alone
explain the power laws? Both are necessary to generate a scale-free
network. A growing network without preferential attachment has an
exponential degree distribution which is similar to a bell curve.
In the absence of growth we are back to the static models.
|
6. 金持ちがより金持ちに:
- 新たなノードが 2つのリンクを持っていると仮定しよう。第 3のノードはそれらいずれのノードともリンクする。第4のノードはリンクを張るノードを３つ選択する。このプロセスを際限なく繰り返すと、新たなノードを付け加える毎に、それにランダムに選択した2つのノードにリンクを張ることになる。この単純なアルゴリズムによって生成されるネットワークをモデルＡと呼ぶとすれば、それはランダムなネットワークとは異なる。
- モデルＡの最初のノードは最もリッチになる、というのはこれらはリンクを張るのに長い時間を費やせるからである。最も貧弱なノードはこのシステムに最後に参加したノードであり、それは２つのリンクしかない。
- 実際のネットワークのリンクはランダムではない。人気こそが引力なのだ。多数とリンクしているウェブページはますますリンクされるようになる。多くのリンクのある俳優には新たな役柄がますます増え、より多く引用される新聞は、ますます引用される度合いが増え、コネクターはより多くの友を作るのである。
- ＜左図＞: 2つの接続ノードからスタート(左上)して、各パネルの新たなノード(赤点)をネットワークに追加する。接続先は、より多く接続されているノードに決める。選択的に接続の成長に従って、非常に多く接続されたハブがいくつか現れてくる。
- 成長と優先接続のいずれかでべき乗則が説明できるだろうか。スケールフリーのネットワークを生成するには両方が必要である。優先接続なき成長ネットワークはベル曲線に似た指数分布となる。成長がなければ静的モデルに戻ってしまう。
|
>Top
7. Einstein's
Legacy:
- The scale-free model reflects our awakening to the reality
that networks are dynamic systems that change constantly through the
addition of new nodes and links.
- The fitness model allows us to describe network as competitive
systems in which node fight fiercely for links.
- Now Bose-Einstein condensation explains how some winners
get the chance to take it all.
- This winner takes all means that the fittest node grabs all
links, leaving very little for the rest of the nodes. Such networks
develop a star topology, in which all nodes are connected to a
central hub.
|
7. アインシュタインの遺産:
- 規模自由モデルは、常に新たなノードと接続が加わることによって常に変化するダイナミックなシステムであるネットワークの現実を想起させる。
- 適応モデルは、各ノードは接続を求めて激しく闘うような競争的なシステムのネットワークを表現している。
- ボーズ・アインシュタイン凝縮モデルは、一部の勝者がすべてを得る可能性を説明している。
- この勝者がすべてを取ることの意味は、最も適応したノードがすべての接続を行い、他のノードの接続は非常に少ないままの状態でいることである。このネットはスター状の接続となり、すべてのノードは中央ハブと接続する。
- 注）ボーズ-アインシュタイン凝縮：
ボーズ-アインシュタイン統計にしたがう粒子が, 低温で, 波数 0 の状態に巨視的な数の粒子がはいる現象（1 つの状態に何個でもはいり得る。）
|
>Top 8. Achilles'
Heel:
- The 1996 blackout:
With thousands of generators, millions of miles of lines, and over
a billion loads, this huge electric animal is now so interconnected
and sensitive that a single disturbance can be detected thousands
of miles away. But the 1996 blackout has highlighted the underlying
vulnerability of this formidable system.
- Natural systems:
It beg to be different, however. Throughout Earth's geological history,
species have disappeared at a rate of one per million each year.
- In general, natural systems have a unique ability to survive
in a wide range of conditions.
- This is in stark contrast to most products of human design.
Therefore, robustness - rooted in Latin robus, meaning
"oak," the symbol of strength and longevity is an increasingly
investigated topic.
- Interconnectivity:
Nature strives to achieve robustness through interconnectivity:
- A cell's robustness is hidden in its intricate regulatory
and metabolic network;
- society's resilience is rooted in the interwoven social
web;
- the economy's stability is maintained by a delicate network
of financial and regulatory organizations;
- an ecosystem's survivability is encoded in a carefully
crafted web of species interactions.
- Network breakdown:
Decades of research indicated that network breakdown is not a gradual
process. Removing only a few nodes will have little impact on the
network's integrity. Yet, if the number of removed nodes reaches a
critical point, the system abruptly breaks into tiny unconnected islands.
- Scale-free network:
Expecting a critical point, we gradually increased the number of
removed nodes of the Internet. We could remove as many as 80% of
all nodes, and the remaining 20% still hung together, forming a
tightly interlinked cluster. The Internet, unlike many other human-made
systems, displays a high degree of robustness against router failures.
- Source of topological robustness:
The distinguishing feature of scale-free networks is the existence
of hubs, the few highly connected nodes. Failures, however,
do not discriminate between nodes but affect small nodes and large
hubs with the same probability.
- Topological robustness is thus rooted in the structural unevenness
of scale-free networks; failures disproportionately affect small
nodes.
- >Top Percolation theory (studies
of random networks):
For scale-free networks the critical threshold disappear in cases
where the degree exponent is smaller or equal to three. Amazingly,
most networks of interest, ranging from the Internet to the cell,
are scale-free and have a degree exponent smaller than three. Therefore,
these networks break apart only after all nodes have been removed.
- Remarks: "Percolation" problem:
When water is flowed from one corner of grid of pipes whose lattice
points are randomly blocked; this is an probability issue. Here
it is known that there is a critical point in this problem.
- >Top Coexistence of robustness and vulnerability:
If crackers launched a successful attack against the largest Internet
hubs, the potential damage could be tremendous.
- If a drug or an illness shuts down the genes encoding the connected
proteins, the cell will not survive.
- Ecosystems can easily survive random species deletions. If the
highly connected keystone species are removed, the ecosystem dramatically
collapses.
- Cascading failure:
Routers do not break down under too much traffic. They simply create
a queue, processing as many packets as they can and dropping the rest.
Only a small percentage of the packets will make it through. Sender
of lost packets does not get a confirmation that its message arrived,
it sends it again, escalating the congestion.
- The discovery of those laws cold have profound implications
for many fields, ranging from the Internet to marketing.
- Achilles' heel:
Topology, robustness, and vulnerability cannot be fully separated
from one another. All complex systems have their Achilles' heel.
|
8. アキレス腱:
- 1996年の停電事故:
何千という発電機、何百万マイルもの送電線、何十億という負荷、この巨大な電力の怪物は今や相互に接続し、何千マイルも離れた所での一つの以上を検知する。だが1996年の停電はこの膨大なシステムに潜む脆弱性をあぶり出した。
- 自然のシステム:
自然のシステムはこれとは全く異なっている。地球上の地質時代を通じて毎年百万分の１の確率で種が絶滅してきた。
- 一般的に、自然のシステムは広範囲の条件の中で生存できる独特の能力を備えている。
- これは人間の設計による多くの製品との明確な違いである。それゆえ、堅牢さrobustの語源はラテン語のoakで、これは強靱と長寿の象徴であり、それはますます重要な研究課題となっている。
- 相互接続:
自然は堅牢さを相互接続することで実現してきた。
- 細胞の堅牢さはその複雑な規則性と代謝のネットワークに潜んでいる。
- 社会の活性は相互に連結した社会的な網にその起源がある。
- 経済の安定性は、金融機関および規制当局の微妙なネットワークで維持されている。
- エコシステムの生存力は、慎重に編み上げられた種族の相互作用の網の中に組み込まれている。
- ネットワークの破壊:
何十年に亘る研究の結果は、ネットワークの破壊は漸進的ではないことを示している。数個のノードを除去してもネットワークの統一性にはほとんど影響がない。しかし除去するノードを増やしてある閾値になるとシステムは急速に小さな孤立した島状に分解してしまう。
- スケールフリー・ネットワーク:
この閾値を求めるために、我々はインターネットの除去するノードを徐々に増やした。我々は全ノードの80%を除去しても、残りの20%で何とか相互接続を保っていた。インターネットは、その他の人工のシステムとは異なり、ルータの故障に対して高度な堅牢性を示している。
- 位相学的な堅牢さの根源:
スケールフリー・ネットワークの際だった特徴は、多くのノードと接続している少数のハブの存在である。 故障はどのノードで起こるか区別しないので、小さなノードも大きなハブも同じ確率で発生する。
- 従って位相学的な堅牢さはスケールフリー・ネットワークの構造的な不平等性にある。それは故障が起こっても、その頻度とは不釣り合いなほど小さなノードに影響を与えるだけである。
- パーコレーション理論:
(ランダム・ネットワーク研究):
スケールフリー・ネットワークでは、閾値はべき指数が３以下の場合にはなくなるのである。驚くべきことに、インターネットから細胞に至るまで、スケールフリーのべき指数は３未満である。それゆえ、これらのネットワークはすべてのノードを除去するまでネットワークは分離しない。
- 注）Percolation理論:
格子状に組み立てたパイプの格子点をランダムに閉塞して、一隅から水を流したときに、他の隅から流出するか問う確率的な問題。なお、この問題には閾値が存在することが知られている。
- 堅牢さと脆弱さの共存:
もし、クラッカーがインターネットの最大のハブを継続的に攻撃したとすれば、その被害は膨大なものになろう。
- もし薬や病気によってタンパク質を結合するコードの書かれた遺伝子が破壊されると、細胞は生存できない。
- エコシステムはランダムな種の滅亡に対しては容易に生存できる。もし高度に結びついた中心的な種が取り除かれると、エコシステムは劇的に崩壊する。
- 連鎖的失敗:
ルータは異常に多くのトラフィックによって壊れたりはしない。それは単に待ち行列を作って、処理可能な量のパケットを処理し残りを廃棄する。少量のパケットだけが到達するのである。パケットをロスした送り手は、メッセージの到達確認が来ないので、再送することになり、それが混雑を増やすことになる。
- これらの法則の発見は多くの分野、即ちインターネットからマーケティングに至るまで非常に参考になる。
- アキレス腱：
トポロジー、堅牢性、および脆弱性は、それぞれ完全には分離できない。すべての複雑なシステムにはアキレス腱がある。
|
>Top
9. Viruses and
Fads:
- Opinion leaders:
Hubs, often referred to as "power users," or "influencers."
- Pfizer study demonstrated that innovations spread from innovators
to hubs. The hubs in turn send the information out along their
numerous links, reaching most people within a given social or
professional network.
- If the hubs resist a product, they form such an impenetrable
and influential wall that the innovation can only fail.
- Threshold model:
We all differ in our willingness to accept innovation.
- >Top Critical threshold:
If the spreading rate of the innovation is less than the critical
threshold, it will die out shortly. If it is over the threshold,
then the number of people adopting it will increase exponentially
- >Top Virus:
- The characteristic life of most viruses ranges between 6 and
14 months. That is, viruses are infecting computers more than
a year after their first occurrence.
- Computer viruses defy the predictions of the classical epidemic
models. On the Internet, computers are not connected to each other
randomly. Rather, the underlying network has a scale-free topology.
Thus, computer viruses should be modeled on a scale-free network instead of the random one used in all previous
studies.
- Scale-free networks are dominated by hubs. Once infected, a
hub can pass the virus to all the other computers it is linked
to.
- The models offer a simple description of spread of ideas, innovations,
and new products and the diffusion of infectious disease. They
capture the process that aids the spread of religions as well.
- As to the number of sexual partners; a study indicated that
the majority of respondents had between 1 and 10 sexual partners
during their lifetime. Some, however, had dozens or more. A few
had several hundred. The distribution followed a power law (scale-free
topology). Once infected, hubs quickly infect hundreds of others.
If our sex web formed a homogeneous, random network, AIDS might
have died out long ago. The scale-free topology at AIDS's disposal
allowed the virus to spread and persist.
|
9. ウイルスと流行:
- オピニオン・リーダ:
ハブ、あるいはパワーユーザ、影響力のある人なども同じ。
- ファイザー社の研究によればイノベーションはイノベータからハブへと広がる。ハブは多くの接続者に対しその情報を送り、社会的あるいは職業的なネットワーク内のほとんどの人に届ける。
- ハブが製品に抵抗する場合、ハブは頑固かつ影響力のある壁を作り、イノベーションは失敗に帰する。
- 閾値モデル:
イノベーションを喜んで受け入れることについてはそれぞれ異なる。
- 限界閾値:
もしイノベーションの拡散率が限界閾値以下の場合、それはまもなく消滅する。もしそれが閾値より大きい場合は、それを採用する人数は指数関数的に増加する。
- ウイルス:
- ほとんどのウイルスの寿命は5 - 14ヶ月である。即ち、コンピュータに感染するウイルスは発生後１年以上経っている。
- コンピュータウイルスは、従来の伝染病モデルの予測に反している。インターネットでは、コンピュータはランダムの相互接続はしていない。ネットワークは従来の研究で使用されていたランダムではなくむしろスケールフリーの構造をしている。
- スケールフリーのネットワークはハブが支配している。一旦感染するとハブはそこに接続しているすべてのコンピュータにウイルスを撒き散らす。
- このモデルは思想、発明、新製品や伝染性の病気にも当てはまる。また宗教の普及についても同じプロセスが成り立つ。
- 性的パートナーの数は、研究によれば回答者の多数は、生涯で１から10名である。一部には12名あるいはそれ以上もいる。少数が数百である。この分布はべき乗則
(スケールフリー)である。一度感染すれば、ハブは速やかに他の数百を感染させる。もし性のWebがホモから成るランダムネットワークであれば、AIDSはとうの昔に死滅しただろう。AIDS感染がスケールフリー構造になっていることがウイルスを拡散し長らえてさせてきた。
|
>Top
10. The Fragmented
Web:
- A few years ago;
we thought we knew everything there was to know about the Web. We
trusted the search engines to convey and deliver the Web to us. This
suddenly changed in April 1998.
- Steve Lawrence, etc. built a meta-search engine, a robot called Inquirus that could inquire at each major search engine
for documents matching a given query.
- For example, of the 1000 documents containing the world "crystal"
found by AltaVista, 343 were on HotBot's list as well. Dividing
the number of overlapping documents by the number of documents
returned by AltaVista give the fraction of the Web covered by
HotBot. Since HotBot report indexed 110 million pages (Dec. 1997),
the group estimated that WWW had about 320 million documents.
(110/0.343)
- Their findings about the search engines' ability to map the
Web offered us little to cheer about.
- The bad news was that HotBot covered only 34% of the full Web.
That is, 66% of all webpages were unseen by it. AltaVista was
second on the list because its robots sniffed out only 28%. Some
search engines, such as Lycos, had captured as little as 2%. Product
manger at Lycos Inc. says, "Our focus is not on quantity,
it's on quality."
- In Feb. 1999;
they repeated their measurements and found that the size of the Web
had more than doubles, swelling to 800 million documents. In fact,
their coverage had further deteriorated: Northern Light, the leader
covering a mere 16%, AltaVista 15%, HotBot 11%, Google 7.8%. The search
engines covered about 40% of the full Web.
- In June 2001;
Google hit a new record; 1-billion-document coverage mark. Alltheweb.com
is second with over 600 million documents, followed by AltaVista with
550 million. The search engines are doing better and better. However,
the Web is growing even faster.
- Most search engines do not even try to reach the full Web. If you
are looking for diffciult-to-find information, the engine with the
larger coverage is your best bet. But when it comes to popular topics,
a larger index does not necessarily offer better results. Most of
us are already overwhelmed by the thousands of hits. Therefore, beyond
a certain point it is more profitable to enhance the algorithm that
selects the best page from the search engine's already enormous database
than to go deeper into the Web.
|
10. 断片化したWeb:
- 数年前は、我々はWeb上で知りたいことはすべて知ることができると思っていた。我々は検索エンジンを信頼しており、それは我々にWebを届けてくれると思っていた。これは1998年4月に突然変わった。
- Steve Lawrence他は、Inquirusと呼ばれるメタ検索エンジンを作成した。これは主な検索エンジンに問い合わせて、ある質問と合致する文章を探すことができる。
- 例えば、AltaVistaによる検索では、"crystal"を含む文章は1000件見つかり、同じくHotBotでは343件見つかったとする。HotBotの調査では110百万ページとのことなので
(1997/12現在)、WWWの総数は約320百万文書となる。(110/0.343)
- これらの検索エンジンでわかったことだが、Webの構造は我々にとっては喜ぶべきものはなかったことを示している。
- 良い話とは言えないが、HotBotは全Webの34%しかカバーしていない。つまり全Webページの66%はそれに発見されていない。AltaVistaはその次で、その検索ロボットは28%を探索した。Lycosの場合はわずか2%である。Lycos社の製品部長曰く「我々の目標は量ではなく、質である」
- 1999年2月:
Webのサイズを再測定したところ２倍以上に膨張していたことが判明した。実際に、検索エンジンによるカバレッジはリーダであるNorthern
Lightが16%、AltaVista 15%、HotBot 11%、Google 7.8%であった。検索エンジンはWeb全体の約40%しかカバーできていない。
- 2001年6月:
Googleが10億文書をヒットする記録を出し、Alltheweb.comは２番の6億文書、AltaVistaは5.5億文書を検索した。検索エンジンはますます改善されてきている。問題は、Webの方が遙かに急速に成長していることである。
- ほとんどの検索エンジンは全Webを探索しようとしていない。もし見つけにくい情報を探しているのであれば、広範囲をカバーするエンジンが最適となる。しかし人気のあるトピックスを対象とするのであれば、大量の索引は必ずしも良い結果をもたらさない。多くのユーザはすでに何千というヒット数で圧倒されてしまっている。従って、ある時点からは、検索エンジンが既に集めたデータベースから最善のページを選択するアルゴリズム能力を高める方が、Web内を深く探索するより有利となる。
|
12. may be continued:
- This "Linked" book still contains important message.
The summary may be added here.
|
この続きあり:
- この「LINKED」の本にはまだ重要なメッセージが含まれている。いずれその要約ここの追記する予定である。
|
