### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 558 Note for PHYS 597A with Professor Albert at PSU

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 20 views.

## Similar to Course at Penn State

## Reviews for 558 Note for PHYS 597A with Professor Albert at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

PENNSTATE E Search in complex networks Hari Prasad Thadakamalla PhD candidate Email hpt102psuedu Department of Industrial and Manufacturing Engineering Local search in networks Search with help of only local oSearCh inth help Of global information Each node has the Informatlon The path information of only neighboring obtained is the shortest path nodes and does not know the position of the destination node 1 9 Start node 30 9 Destination node Path obtained is shown in dashed line Milgram s experiment 1960 s 7 e I Social network 4 Nodes People quot Edges Acquaintances Wife of divinity school student Connected by an edge if A and B know each other letter steps jte Targeted person has to receive the Rules 1 Each person can give the letter only to his her acquaintances 2 Choose the acquaintance such that it will reach the target person as quickly as possible 9 Short chains of acquaintances exist Six degrees of separation 9 People were able to find these chains using only local information 3 Results in literature gt Many network models have been proposed explaining the first observation gt Second observation implies that the structure of the network is inherently searchable Searchability 9 Search length scales as log N or lesser gt Kleinberg 2000 demonstrated that emergence of the second phenomenon requires special topological structure gt Watts et a1 2002 model explains this phenomenon based on plausible hierarchical social structures Kleinberg s model 0 Gndpqr O O O O O O n number ofnodes 0 d dimension 0 p distance for local neighbors q number of longrange connections P duv Gn211 r Distance between nodes is lattice distance or L1 norm dz39j um lk z391 Jl Kleinberg s model cont gt Generalization of Watts and Strogatz model 9 Rich in local connections few longrange connections 9 When r 0 it is similar to WattsStrogatz model gt Objective 9 Send a message from node u to target node t gt Known information 9 Set of local contacts among all nodes underlying grid structure 9 Grid position of the target node t Kleinberg s model cont gt Algorithm 9 Greedy algorithm Send the message to the neighbor which ever is closer to the target node gt Results 9 There is a decentralized algorithm A and a constant 0L1 independent of n such that when r 2 and p q 1 the expected delivery time of A is at most 0L1 log n2 o For 0 S r lt 2 any decentralized algorithm at least ocrna39rW o For r gt 2 any decentralized algorithm at least arnltr2gtltr1gt Kleinberg s model cont 8 r 2 r 1 lower bound T 5 2 r3 0L1 delively tune given as lognT clustering exponent 139 Identity and search in social networks Watts et al gt Presented a model based upon plausible social structures and contentions about social networks Individuals into set of groups 4 research labs Layers of groups university Longrange connections I 117 1 Different hierarchical clusters H 2 7quot 39 J occupation Social distance Identity and search in social networks cont 12 10 A G8 56 4 2 39 12 3 4 5 6 7 8 9101112131415 L Comparison between nL the number of completed chains of length L taken from the original smallworld experiment bar graph and from an example ofthe model given by Watts eta with N 108 individuals 10 Search in powerlaw networks Adamic et LIL gt Search in nonspatial networks gt Adamic et al 2001 showed that high degree seeking strategy is better than random walk strategy 9 Random walk Number of steps 5 to reveal the whole graph is s N N3172r 9 High degree search NE UtilizesHaemeteteqjamq liee in the node degree S N N274 11 Real networks are heterogeneous in edge weights gt Edgeweight Distribution The distribution of the edgeweights in the network 9 Many real networks have heterogeneous edgeweights 0 Internet Amount of traf c or bandwidth available 0 Social network Strength of acquaintance 0 Metabolic networks Strength of interactions 0 Sensor networks Amount of energy consumed 0 Transportation network Distance cost 9 No empirical results gt Optimal strategy may change 39f the ed e weights are different weighted complex etworks Heterogeneous edgeweights 12 Local betweenness centrality LBC Thadakamalla et 111 gt Form the local network consisting of the root node first and second neighbors root node Neighbors 2 3 4 and 5 13 LBC cont gt Form the local network consisting of the root node first and second neighbors gt LBC of the first neighbor i Li 2 LG Siiil as SJE local network 039 is the total number of shortest paths om node s to l O39Srl39 is the number of these shortest paths passing through i o Shortest path 5 t The path from node 5 to node t which has the smallest sum of edge weights 14 LBC of a neighbor depends on both the degree of the neighbor and the weight on the edge connecting it to the root root39node Neighbors 2 3 4 5 a L2 760 L3 420 L4 420 L5 00 b L2 760 L3 920 L4 420 L5 00 15 Highest LBC algorithm performs best in powerlaw networks Powerlaw exponent 21 23 25 27 29 Search strategy Random walk 110870 176058 271311 389491 476975 Minimum edge weight 31895 74541 153923 273201 378956 Highest degree 37583 76145 151974 269362 373961 Minimum average node weight 60541 106534 187043 304227 393603 Highest LBC 29806 70725 149048 266774 375153 Comparison of different search strategies in powerlaw network on 2000 nodes with different powerlaw exponents The edge weights are generated from an exponential distribution with mean 5 16 The difference between the highdegree search and highLBC search increases as the heterogeneity in edge weights increase Beta 5 5 Uniform0 10 Exp Powerlaw Search strategy o2 23 02 83 O2 25 02 246538 Random walk 110771 109772 110870 101121 202 241 272 344 70447 41471 31895 35854 Minimum edge weight 92 29 7 44 Hi best de me 37998 36843 37583 46618 g g 4 14 26 59 122868 78815 60541 46618 Minimum average node weight 235 145 103 88 Highest LBC 36626 32230 29806 24777 Power law network with exponent 21 on 2000 nodes The values in the brackets show the percentage increase in average distance for each strategy relative to the average distance taken by the LBC strategy 17 Pictorial comparison High degree Search Normalized average distance High LBC Search Heterogeneity of edge weights The pictorial comparison of the behavior of highdegree and highLBC search as the heterogeneity of edge weights increases in powerlaw networks Note that average distances are normalized with respect to high LBC search 18 References gt S Milgram The SmallWorld Problem Psychology Today 1 1967 gt 2OIlteinberg Navigation in a small world Nature 406 24 August gt Kleinber3 The small world phenomenon An algorithmic perspective roc 32nd ACM Symposium on Theory of Computing 2000 gt DJ Watts PS Dodds and ME Newman Identity and search in social networks Science 296 17 May 2002 gt LA Adamic RM Lukose AR Puni ani and BA Huberman Search in powerlaw networks Physical eview E 64 046135 2001 gt HP Thadakamalla R Albert and SRT Kumara Search in weighted complex networks Physical Review E 72 066128 2005 gt Kleinberg Complex Networks and Decentralized Search Algorithms Proceedin s of the International Congress of Mathematicians IC 2006 to appear 19 Questions 20

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.