(original) (raw)
��ࡱ�>�� ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������� e�(���� J * ]����Sep 03 stats:�xhttp://www.searchenginewatch.com/reports/article.php/2156481�J��visualization�webmap.pdf�n��8remove high-degree vertices?�webnohubs.pdf�R��heavy-tailed�webpowerlaw.pdf��� �examples�`http://www.cs.cornell.edu/home/kleinber/auth.pdf����&PageRank calculator�fhttp://www.webworkshop.net/pagerank\_calculator.php3��/� 0��0�DArialgs����PL�����0�:A 0��DComic Sans MSPL�����0�:A 0�B �DWingdings MSPL�����0�:A 0�0�DSymbolgs MSPL�����0�:A 0�� �A��� .� @�n��?" d�d@������� @@``�� ����`��j #;>[:\bcfghijklmnopqrstuvwxyz{| } �� �0���A���A� ���@��������������ʚ;���ʚ;�g��4IdId �:A 0P�������p�pp�@ <�4ddddL��$ 0��(L�� ��0�___PPT10� �����___PPT9������������ ��?� � %��U��P��The Web as Network�(����8Networked Life CSE 112 Spring 2006 Prof. Michael Kearns �9Z9���=��The Web as Network�(�����Consider the web as a network vertices: individual (html) pages edges: hyperlinks between pages will view as both a directed and undirected graph What is the structure of this network? connected components degree distributions etc. What does it say about the people building and using it? page and link generation visitation statistics What are the algorithmic consequences? web search community identification ��t'/9/'&�V����� ����'�/�9�/� � � �� � &�����A��0Graph Structure in the Web [Broder et al. paper]�@1(����(�����<Report on the results of two massive web crawls Executed by AltaVista in May and October 1999 Details of the crawls: automated script following hyperlinks (URLs) from pages found large set of starting points collected over time crawl implemented as breadth-first search have to deal with webspam, infinite paths, timeouts, duplicates, etc. May 99 crawl: 200 million pages, 1.5 billion links Oct 99 crawl: 271 million pages, 2.1 billion links Unaudited, self-reported Sep 03 stats: 3 major search engines claim > 3 billion pages indexed �0w�%%(7w������G��%��%�( � 7 � � �<"� 9��B 0�����B��Five Easy Pieces �(�����Authors did two kinds of breadth-first search: ignoring link direction �� weak connectivity only following forward links �� strong connectivity They then identify five different regions of the web: strongly connected component (SCC): can reach any page in SCC from any other in directed fashion component IN: can reach any page in SCC in directed fashion, but not reverse component OUT: can be reached from any page in SCC, but not reverse component TENDRILS: weakly connected to all of the above, but cannot reach SCC or be reached from SCC in directed fashion (e.g. pointed to by IN) SCC+IN+OUT+TENDRILS form weakly connected component (WCC) everything else is called DISC (disconnected from the above) here is a visualization of this structure�</_6$=?5�/�����-�����6�$�,� ���� � � � ��6 � �� ���'�����y����� B 0�����C��Size of the Five�(����tSCC: ~56M pages, ~28% IN: ~43M pages, ~ 21% OUT: ~43M pages, ~21% TENDRILS: ~44M pages, ~22% DISC: ~17M pages, ~8% WCC > 91% of the web --- the giant component One interpretation of the pieces: SCC: the heart of the web IN: newer sites not yet discovered and linked to OUT: insular pages like corporate web sites�`�y�����"�y���D��Diameter Measurements�(����"Directed worst-case diameter of the SCC: at least 28 Directed worst-case diameter of IN �� SCC �� OUT: at least 503 Over 75% of the time, there is no directed path between a random start and finish page in the WCC when there is a directed path, average length is 16 Average undirected distance in the WCC is 7 Moral: web is a small world when we ignore direction otherwise the picture is more complex�P) 0 b44V)� �0� ��������8�4� � � ��! � V���E��Degree Distributions�(�����They are, of course, heavy-tailed Power law distribution of component size consistent with the Erdos-Renyi model Undirected connectivity of web not reliant on connectors what happens as we remove high-degree vertices? ��L&;0<�����&�;�0���: ? U�� B 0�!�� B 0�����F��Beyond Macroscopic Structure�(�����Such studies tell us the coarse overall structure of the web Use and construction of the web are more fine-grained people browse the web for certain information or topics people build pages that link to related or similar pages How do we quantify & analyze this more detailed structure? We ll examine two related examples: Kleinberg s hubs and authorities automatic identification of web communities PageRank automatic identification of important pages one of the main criteria used by Google both rely mainly on the link structure of the web both have an algorithm and a theory supporting it ��ss_!/ Ve ��������� ���"�s�_� ����/� � V � � � ��? � �,�Pf��G��Hubs and Authorities�(����Suppose we have a large collection of pages on some topic possibly the results of a standard web search Some of these pages are highly relevant, others not at all How could we automatically identify the important ones? What s a good definition of importance? Kleinberg s idea: there are two kinds of important pages: authorities: highly relevant pages hubs: pages that point to lots of relevant pages If you buy this definition, it further stands to reason that: a good hub should point to lots of good authorities a good authority should be pointed to by many good hubs this logic is, of course, circular We need some math and an algorithm to sort it out��:Z.Z�ZTZ>Z�Z2Z:�.�H� ���,� ���J� ������� �����>���2���H��0The HITS System (Hyperlink-Induced Topic Search)�11$�����Given a user-supplied query Q: assemble root set S of pages (e.g. first 200 pages by AltaVista) grow S to base set T by adding all pages linked (undirected) to S might bound number of links considered from each page in S Now consider directed subgraph induced on just pages in T For each page p in T, define its hub weight h(p); initialize all to be 1 authority weight a(p); initialize all to be 1 Repeat forever : a(p) := sum of h(q) over all pages q �� p h(p) := sum of a(q) over all pages p �� q renormalize all the weights This algorithm will always converge! weights computed related to eigenvectors of connectivity matrix further substructure revealed by different eigenvectors Here are some examples���\Vn%x� ����0��������k�\� ���������n� � � ��x � � ���I+, ��� B 0�����I��The PageRank Algorithm�$��� ���Let s define a measure of page importance we will call the rank Notation: for any page p, let N(p) be the number of forward links (pages p points to) R(p) be the (to-be-defined) rank of p Idea: important pages distribute importance over their forward links So we might try defining R(p) := sum of R(q)/N(q) over all pages q �� p can again define iterative algorithm for computing the R(p) if it converges, solution again has an eigenvector interpretation problem: cycles accumulate rank but never distribute it The fix: R(p) := [sum of R(q)/N(q) over all pages q �� p] + E(p) E(p) is some external or exogenous measure of importance some technical details omitted here (e.g. normalization) Let s play with the PageRank calculator ��^^^� �(;�����^�� ���������� �D� ���� ���P�( � ���^5� N� � ��B 0�����J��2The Random Surfer Model�$����Let s suppose that E(p) sums to 1 (normalized) Then the resulting PageRank solution R(p) will also be normalized can be interpreted as a probability distribution R(p) is the stationary distribution of the following process: starting from some random page, just keep following random links if stuck in a loop, jump to a random page drawn according to E(p) so surfer periodically gets bored and jumps to a new page E(p) can thus be personalized for each surfer An important component of Google s search criteria ��^D>�3^�D� ������� ����4���, K�>E��K��But What About Content?�$�����PageRank and Hubs & Authorities both based purely on link structure often applied to an pre-computed set of pages filtered for content So how do (say) search engines do this filtering? This is the domain of information retrieval �� g^ � ����;����H���������L��Basics of Information Retrieval� $����vRepresent a document as a bag of words : for each word in the English language, count number of occurences so d[i] is the number of times the i-th word appears in the document usually ignore common words (the, and, of, etc.) usually do some stemming (e.g. washed �� wash ) vectors are very long (~100Ks) but very sparse need some special representation exploiting sparseness Note all that we ignore or throw away: the order in which the words appear the grammatical structure of sentences (parsing) the sense in which a word is used firing a gun or firing an employee �8*P'w#*��� ���A����6����'�Y�����#���>a ���M�� Bag of Words Document Comparison�!!$����dView documents as vectors in a very high-dimensional space Can now import geometry and linear algebra concepts Similarity between documents d and e: S d[i]*e[i] over all words i may normalize d and e first this is their projection onto each other Improve by using TF/IDF weighting of words: term frequency --- how frequent is the word in this document? inverse document frequency --- how frequent in all documents? give high weight to words with high TF and low IDF Search engines: view the query as just another document look for similar documents via above ���ZcZ,Z�ZZPZ����r���F� ���������/����:����>��P � �,��/���������������� ��!��"��#��$��%��&��'��� � `� ���������33�����`� ��������S��f�3�f`� ������������33��g�`� ������������f��`� ���www���3���PP��`� �����ZX���dbmo����`� ����\�ғ�3�y`���Ӣ`� ����3f���3f��f����`� ���3f����3�F�Kf����`� hk]���www�����������f�ܹ`� ff����>>\���`Y{ff�������`� R>&���- ����{p�_/̴����>��?" d�d@�������,�|��?" d�d�@������� � � �" �@� �`��� �n��?" d�d@������� @@``��P�R @ ` �`� p�>��> �����f�( � ��� � � �6�P�������� �� `}�� � �T�� Click to edit Master title style�!� !� � � �0�艑����� �� `�� � ���RClick to edit Master text styles Second level Third level Fourth level Fifth level�! � S� � � �0��������� �^ `��� � �>��*��� � � �0�X������� �^����� � �@��*��� � � �0� ������� �^ `��� � �@��*���H � � �0�������h�� ?� ���������33������8�0�___PPT10��.f���6�� �Default Design���� 0 z�r0�,� �( � �,�� �, � �0�������� �P �� � �P��*� �� �� �, � �0� ������ �� � �� � �R��*� �� �d �, c �$��� ?��� �� �� �, � �0�T������ �� �0��� � ���RClick to edit Master text styles Second level Third level Fourth level Fifth level�! � S�� �, � �6��������� �_P�� � �P��*� �� �� �, � �6��������� �_� ��� � �R��*� �� �H �, � �0���h������ ?� ���������33������8�0�___PPT10��.-��I�<���� �����0�( � ���x �� c �$��y������`�� � � ��x �� c �$�Pz������P`� �� � � ��H �� � �0�������h�� ?� ���������33����������___PPT10�i�.f��P���+D�='� �����=� @B� +��� � �����9 �\�( � � �x � c �$��I���������� � � �� � c �$��J�����0�� �<$� 0� � � ��H � � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�$'� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* @%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* @`%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* `�%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* �!%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* !:%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* :P%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* Pw%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* w�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�+8+0+ � +��� � ��� �(�\�( � �(�x �( c �$�T���������� � �� �( c �$�P������0�` �<$� 0� � ��H �( � �0�������h�� ?� ���������33������w�o�___PPT10�O�.f����b�+�[W_D��'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(2%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(2`%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(`w%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(w�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(W%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(Wf%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(f�%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*(�%�(�+8+0+( +� � � ���`�8�\�( � �8�x �8 c �$�h۪����`��p�� � � �� �8 c �$�dܪ����PP�<$� 0� � � ��H �8 � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�]'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8/%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8/[%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8[�%�(�D��'� �=�%�(�����D�|'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8�%%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8%3%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*83r%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8r�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8�I%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8I�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*8��%�(�+8+0+8� +��� � �����@�\�( � �@�x �@ c �$��������`��p�� � � �� �@ c �$���������P��<$� 0� � � ��H �@ � �0�������h�� ?� ���������33������\�T�___PPT10�4�.f����b�+�[W_D��'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@,%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@,B%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@B]%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@]s%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@s�%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*@ ;%�(�+8+0+@� +� � � �����H�\�( � �H�x �H c �$��������`��p�� � � �� �H c �$���������P��<$� 0� � � ��H �H � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�p'� �����=� @B� D�+'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H)%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H)5%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H5e%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Her%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Hr�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H4%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H4<%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*H<l%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Hl�%�(�+8+0+H� +�� � � �����P�\�( � �P�x �P c �$�������`��p�� � � �� �P c �$�亦�����P��<$� 0� � � ��H �P � �0�������h�� ?� ���������33������� �� �___PPT10�w �.f����b�+�[W_D� '� �����=� @B� D�� '� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*P"%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*P"L%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*PLr%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Pr�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*P��%�(�+8+0+P� +�;� � �����X�\�( � �X�x �X c �$�ͦ����`��p�� � � �� �X c �$�Φ�����P��<$� 0� � � ��H �X � �0�������h�� ?� ���������33��������___PPT10���.f����b�+�[W_D�'� �����=� @B� D�F'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X=%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X=s%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Xs�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X�!%�(�D�p '� �=�%�(�����D� '� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X!E%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*XEf%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Xf�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X�&%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*X&X%�(�+8+0+X� +�K� �! ����`�\�( � �`�x �` c �$������`��p�� � � �� �` c �$�������P��<$� 0� � � ��H �` � �0�������h�� ?� ���������33������'��___PPT10���.f����b�+�F��D�'� �����=� @B� D�V'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`:%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`:h%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`h�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`=%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`=`%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*``�%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`;%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`;^%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*`^�%�(�+8+0+`� +�f!� �" ��� �h�\�( � �h�x �h c �$�������`��p�� � � �� �h c �$�x������P��<$� 0� � � ��H �h � �0�������h�� ?� ���������33������B�:�___PPT10��.f����b�+�F��D�'� �����=� @B� D�q'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h`%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h`�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h9%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h9a%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*ha�%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h4%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h4t%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*ht�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*h��%�(�+8+0+h� +��� �# ���@�p�\�( � �p�x �p c �$�������`��p�� � � �� �p c �$��������P��<$� 0� � � ��H �p � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�[W_D�'� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p@%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p@^%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p^�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p�%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*pH%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*pH�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p��%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p>%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p>w%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*pw�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*p��%�(�+8+0+p� +�p� �$ ���`�x�\�( � �x�x �x c �$�|������`��p�� � � �� �x c �$�x�������P��<$� 0� � � ��H �x � �0�������h�� ?� ���������33������L�D�___PPT10�$�.f����b�+�[W_D��'� �����=� @B� D�{'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x/%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x/^%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x^q%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*xq�%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x�!%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x!c%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*xc�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*x�%�(�+8+0+x� +�� � �% �������\�( � ���x �� c �$��������`��p�� � � �� �� c �$���������P��<$� 0� � � ��H �� � �0�������h�� ?� ���������33������� �� �___PPT10�w �.f����b�+�F��D� '� �����=� @B� D�� '� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*� D%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�D�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�+8+0+�� +�B� �& �������\�( � ���x �� c �$��Ϡ����`��p�� � � �� �� c �$��Р�����P��<$� 0� � � ��H �� � �0�������h�� ?� ���������33��������___PPT10���.f����b�+�F��D�'� �����=� @B� D�M'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�� '� �=�%�(�����D� '� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�*%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�*l%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�l�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�C%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�Cz%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�z�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�;%�(�+8+0+�� +��$� �' ���� ��8�( � ���� �� � �0�������� ��"�6����������� ���������?�`��p�� � � �� �� c �$��������P��<$� 0� � � ��D�l �� �� ���� ``P�,$�D 0�`B ��� � �0D����Ԕ���� ��`B ��� � �0D���Ԕ���� � ���>�l �� �� � ��� `�P�,$�D 0�`B �� � �0D���Ԕ��� �@�ZB ��B s �*D���>���� ���H �� � �0�������h�� ?� ���������33����������___PPT10�w�.f����b�+k��D�'� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�;%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�;o%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�o�%�(�D�4'� �=�%�(�����D��'� =�%�(�D�'� =�4@B��B��B��B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���������%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�4'� �=�%�(�����D��'� =�%�(�D�'� =�4@B��B��B��B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ���������%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��$%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�$b%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�b�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*� 2%�(�+8+0+�� +��= 0 �����(�( � ��^ � S ���,���� �� ��� � c �$�����,��� �0��� � ��� �H � � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��A 0 ��0�,�(�( � �,�^ �, S ���,���� �� ��� �, c �$������,��� �0��� � ��� �H �, � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��B 0 ��p�<�(�( � �<�^ �< S ���,���� �� ��� �< c �$�\���,��� �0��� � ��� �H �< � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��C 0 ����D�(�( � �D�^ �D S ���,���� �� ��� �D c �$�����,��� �0��� � ��� �H �D � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��D 0 ����L�(�( � �L�^ �L S ���,���� �� ��� �L c �$�X���,��� �0��� � ��� �H �L � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��E 0 ����T�(�( � �T�^ �T S ���,���� �� ��� �T c �$������,��� �0��� � ��� �H �T � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��F 0 ����\�(�( � �\�^ �\ S ���,���� �� ��� �\ c �$�p����,��� �0��� � ��� �H �\ � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��G 0 ���d�(�( � �d�^ �d S ���,���� �� #�� �d c �$�<#��,��� �0��� # ��� �H �d � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��H 0 ��0�l�(�( � �l�^ �l S ���,���� �� #�� �l c �$��#��,��� �0��� # ��� �H �l � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��I 0 ��P�t�(�( � �t�^ �t S ���,���� �� #�� �t c �$�T #��,��� �0��� # ��� �H �t � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��J 0 ��p�|�(�( � �|�^ �| S ���,���� �� #�� �| c �$��#��,��� �0��� # ��� �H �| � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��K 0 ������(�( � ���^ �� S ���,���� �� #�� �� c �$�l#��,��� �0��� # ��� �H �� � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��L 0 ������(�( � ���^ �� S ���,���� �� #�� �� c �$��#��,��� �0��� # ��� �H �� � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��M 0 ������(�( � ���^ �� S ���,���� �� #�� �� c �$��##��,��� �0��� # ��� �H �� � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8r� eJ�n� Twp�� 0�����Ӱ������p������c �&0�P��Cp�ge��<��������������t�Pm0� �������Oh��+'��0� `h�� �� � � ����Networked Nature of SocietyCISCIS108Microsoft PowerPointoci@���B�@P��g��@���و-��G������g Z% ������-����- @ !��������--'������@BComic Sans MS-. �"2 ��The Web as Network' :!.&.��"System ��-�����@BComic Sans MS-. 33�2 �dNetworked Life .-�����@BComic Sans MS-. 33�2 ��CSE 112.-�����@BComic Sans MS-. 33�2 ��Spring .-�����@BComic Sans MS-. 33� 2 � 2006.-�����@BComic Sans MS-. 33�%2 1Prof. Michael Kearns" .-�����՜.��+,��D��՜.��+,����������� � �� � :�On-screen ShowUniversity of PAb��{ ArialComic Sans MS WingdingsSymbolDefault DesignThe Web as NetworkThe Web as Network1Graph Structure in the Web [Broder et al. paper]Five Easy Pieces Size of the FiveDiameter MeasurementsDegree DistributionsBeyond Macroscopic StructureHubs and Authorities1The HITS System (Hyperlink-Induced Topic Search)The PageRank AlgorithmThe �Random Surfer� ModelBut What About Content? Basics of Information Retrieval!Bag of Words Document Comparison Fonts UsedDesign Template Slide Titles 8@ _PID_HLINKS�A�$=http://www.searchenginewatch.com/reports/article.php/2156481 webmap.pdfwebnohubs.pdfwebpowerlaw.pdf1http://www.cs.cornell.edu/home/kleinber/auth.pdf4http://www.webworkshop.net/pagerank\_calculator.php3�\_������CISCIS !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~������������������������������������������������������������������������������������������������������������������������������������ ���� ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������Root Entry����������d�O�����)�����Current User������������SummaryInformation(��������PowerPoint Document(�����DocumentSummaryInformation8������������ ������������������������������������