### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Group Study MAE 298

UCD

GPA 3.78

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Engineering Mechanical & Aero

This 133 page Class Notes was uploaded by Consuelo Herman DDS on Tuesday September 8, 2015. The Class Notes belongs to MAE 298 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/187472/mae-298-university-of-california-davis in Engineering Mechanical & Aero at University of California - Davis.

## Popular in Engineering Mechanical & Aero

## Reviews for Group Study

### 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: 09/08/15

Urbanization and Economies of Scale Topics in Network Theory Nicholas J Linesch Institute of Transportation Studies University of California Davis May 12 2009 C iHiineE Outline of Part 0 Context for transportation networks 0 Motivation 0 Terms and Definitions C iHiineE Outline of Part II Urban Systems 0 The Modern City 0 Using software to simulate urbanization C We J Part Context Setting a Goods Ch dren m Jakarta a People 0 Information Thanks to Shawn I l m mm hm Mm mm m m swam WWW gm m yum manqung mewmj o How do these modes Interact7 o What other systems are Impacted by movement and flow7 a How are land use and transportation plans sensItIve to one another7 I n 1 EHHWDHE Network Properties Defining a network A set of nodes or vertices joined together in pairs by lines or edges ii quotquot39 1 ieiiiiiiigiiz Networks and Mathematics iiii Jiiiil39ii W Given a set of things that want39 to move between a set of spatial points V what39s the cheapest way to get them there Gastner amp Newman 2006 wants us to think about two specific parts of this question as applied to transportation networks 0 How do we determine the points V anyway 0 What do we mean by cheapest39 Does how we measure cost change the optimal structure Wueiiner on spaciai distribution network 2009 I i n 1 ElmllloliE Network Properties 0 Cost 2 do where do is the Euclidean distance between edgesij nodes i and j 0 Cost can be measured in travel time and can be influenced by traffic 0 Let WU be the amount of traffic between i and j a Total Travel Cost can be calculated as Z Z Wadi ilti WP 3041 6431mm 4 i o Euclidean distance 0 Legs of air travel 0 Hops an Internet packet will make 1 Largest graph distance between two points I iL J rem v 39 imm im ikmwmii 39 n 1 Darwinian Network Properties Vertex Degrees The degree of a vertex is the number of edges connected to it gt A distinguishing characteristic of a network L Ilnull39J E m 35mm u 1 ehnmmz Interstate Rail System 9 Alr Network 7 m u quotquotquotquot 39 1 Lemma Counting Network Edges sttograms of the engths of edges m three networks Gastner XL Newman 2006 SmaH wor ds formed m awhnes I l LogoftheRank t quot 9 P OUl iUINUImmbKUIU39I 9 550 650 750 850 950 Log oi the Papulaiion igure Log Size versus Log Rank of the 135 largst U S Metropolitan Areas In 1991 Source Statistical Abstract of the United Stats 1993 Part II Urban Systems Analysis 9 Urban Systems 0 The Modern City 0 Using software to simulate urbanization m Scaling and Biological Metaphors Organisms as metabolic engines Characterized by energy consumption rates growth rates body size and behavioral times Cities as organisms m Scaling and Biological Metaphors o A metabolic engine is a consumer of resources 0 Consider biological scaling 0 Almost all physiological elements scale with body mass M Scaling and Biological Metaph Generalized Case 0 Consider M as a body mass 0 M has a metabolic rate B o B is the energy required to sustain the organism o B olt Mg typically the exponent is a multiple of 14 or 11d in ddimensional space y Xao 71 0 The metabolic rate per unit mass olt MT I l Scaling and Biological Metaphors Examples o M149 x Ml4 can be used to scale physiological times life spans turnover time etc Scaling and Biological Metaphors Examples o M149 x Ml4 can be used to scale physiological times life spans turnover time etc o M149 x M l4 can be use to scale associated rates heart rate population growth Scaling and Biological Metaphors Generalizable Items 0 Rates 0 Times 0 Internal structures Bettencou rt equation Bettencourt et al 2007 go on further to describe urban growth and decay with a power law function Yf YONW 1 Where N is the population Y is material resources such as energy or infrasturcture Y0 is a normalization constant e m Application to the Modern City a Data collected to understand scaling of the urban metabolism 0 Data is grouped by metropolitan statistical areas MSAs and larger urban zones LUZs o The data set is applied to the scaling equation described in the previous slide 1115 my 2 metmvuhtzn woman in Suvemveztwe emv wment Dev MSA vs metmvuhtzn Duvuhtmn I l N 39 39 mm W in Heart vztevs m me miss Muvgamsms I l Introduction to Land Use Modeling Software 9 Software package 9 Built by team at University of Washington 0 Open source software used for simulating growth of metropolitan regions a Series of discrete choice models is run to determine the final land use outputs UrbanSIm Land Use Modelm Key Features of the System 9 Simulates key decision makers and choices that impact urban development 0 Accounts for land structures and occupants 0 Urban development simulated as dynamic process over time and space 0 Incorporates governmental policy assumptions 0 Returns disaggregate information by parcel o Simulates development and redevelopment Key Features of Implementation Linux Mac OS and Windows compatible Code predominantly implemented in Python Open source and downloadable User interface focusses on model configuration data management and scenario evaluation Object oriented programming Results are GIS compatible Binary files used for reading and writing can be converted to shapefile database etc 13 V 677 V x 5 a hneamnyparameters funcmon and La 5 a vector of k esumator coef cwents 1 s an mdex over 2H posswb e a ternamves x K r j39 39 mm M wwwa m Sub model routines 0 Real estate price model 0 Household relocation choice model 0 Building transition model 0 Household location choice model 0 Household transition model createsand determines rodseroidsrormovmg usinga legit model removes households and updates the set of persons accordingly ll is based on random sampling and is driven 39 39 b m o Busmess relocation model acroeconomic predictions 9 Business transition model 0 Business location choice model Urban gnwm fun mmgm mm L WW3 C Vy Etfhii39h San Francisco Business Loc Model Growth by 2010 A mummam m Warm mm m Wm WM Business Loc Model Growth by 2020 A mummam m Warm mm m Wm WM Business Loc Model Growth by 2030 wmwm m Warm mam rm mamm39mai T I 1 A Quick Video Presentation of UrbanSim Goto httpwwwyoutubecomwatch7vnm BnRAdeSXw Figure Year 2001 0 O quotC E D 5quot O 5 O 1 O E 9 7 5 U D 5 1 D 5 Q m 0 O Urn Population Growth in San Francisco 1Il 1 I 3 aswwts 39 am a a Figure Year 2010 o L 2 U C U L U C 0 an E J 4 E o L L9 C 9 4 m 3 Q o a Figure Year 2020 15 gal l39 155 II39 335 Aura Big 4 quotV Figure Year 2030 Figure Year 2001 Figure Year 2010 Figure Year 2020 Figure Year 2030 The Mod 7 Mac Urban us quotm Procedures Jobs by Sector in San Francisco Year 2001 Urban Swstems and Jobs by Sector in San Francisco 39 numb um Yransun39uuan was 2m mm ms Year 2010 Ag Hm R um Yransun39uuan was Year 2020 Year 2030 a your 2m VFW ms Content Delivery Networks Shaxun Chen April 21 2009 KW Outline Introduction to CDN An Industry Example Akamai Research Example CDN over Mobile Networks Conclusion Outline gt Introduction to CDN An Industry Example Akamai Research Example CDN over Mobile Networks Conclusion What is Content Delivery Network A content delivery network CDN a system of computers computing devices networked together across the Internet that cooperate to deliver content to end users in order to improve performance scalability and cost efficiency Distributed system Transparent to end users Motivation Request load overwhelms the web sites Web server processing ability Bandwidth Backend transactionprocessing infrastructure 15 billion visits per day 02 billion videos viewed every day 54 billion visits per day ALL YOUR VIDEO ARE BELONG TO US If customers will complain Speed Availability Approaches to Delivering Content Single Server Mirrors EECDN Approaches to Delivering Content Single Server Mirrors EECDN Approaches to Delivering Content Single Server Mirrors CDN Concepts or Terms Servers Origin server Surrogate servers Edge servers Roles CDN providers Akamai Digital Island CDN customers Yahoo AOL CNN Clients end users Advantages of CDN Reduce backbone bandwidth costs Improve end user performance Shorter latency response quickly Less delay jitter Higher bandwidth Increase global availability of content CDN vs Web Proxies First Web proxies store most frequently or most recently requested content work in a passive way What CDNs store is decide by CDN administrators Second Web proxies only handle static web pages Dynamic content secured content streaming content CDN handles them using ESI Third Proxies work on a local basis CDNs provide more availability Best Surrogate Server From endusers clients point of view which surrogate server is the best Nearest physical distance Speed bandwidth Delay roundtrip time delay jitter Reliability packet loss rate Data transmission cost Server load Combinations of the above Placement of Surrogate Servers 1 e We have N ossible locations at edge of the Internet and are ab e to afford K KltV surrogate servers how to place them to minimize the total cost Cost metrics Refers to choose best surrogate server Formalization Minimum K Median Problem Given N points we must select K of these to be centers surrogate servers and then assign each in ut point j to the selected center that is closest to it I location j is assigned to a center i we incur a cost dCf The goal is to select K centers so as to minimize the sum of the assignment costs NPhard 1 L Qiu et al On the Placement of Web Server Replicas Infocom 2001 Alaska US Treebased Algorithm 2 Two assumptions The network structure is a tree the origin server is the root of the tree Clients request from the closest surrogate server on their path toward the root Based on these two assumptions we are able to get a optimum placement within OV3 439 2 B Li et aI On the Optimal Placement of Web Proxies in the Internet Infocom 1999 New York US Greedy Algorithm 7 Chooses the first center with minimum cost among N places chooses next center among rest of 1 places Time complexity OUVZK Greedy Algorithm 7 Chooses the first center with minimum cost among N places chooses next center among rest of 1 places Time complexity 0NZK Greedy Algorithm 7 Chooses the first center with minimum cost among N places chooses next center among rest of 1 places Time complexity 0NZK Places surrogate servers near the clients generating the greatest load Sorts the V potential sites according to the amount of traffic generated within their vicinity and places the surrogate server at the top K sites A s vicinity is the circle centered at A with some radius We change the radius repeat the algorithm and choose the best one as output Time complexity N2 NogV V OVZ Places surrogate servers near the clients generating the greatest load Sorts the V potential sites according to the amount of traffic generated within their vicinity and places the surrogate server at the top K sites A s vicinity is the circle centered at A with some radius We change the radius repeat the algorithm and choose the best one as output Time complexity N2 NogV V OVZ Places surrogate servers near the clients generating the greatest load Sorts the V potential sites according to the amount of traffic generated within their vicinity and places the surrogate server at the top K sites A s vicinity is the circle centered at A with some radius We change the radius repeat the algorithm and choose the best one as output Time complexity N2 NogV V OVZ Random Algorithm Chooses K sites from N places randomly performs 10 times and get the best result o Time complexity OVK CDF n Evaluation Results 300 nodes tree amp a subset of Trace l and 3 300 nodes graph and a subset of Trace l and 3 100 100 m w I A v1 90 7 7 90 80 80 70 70 60 g 60 50 50 40 V 40 Tree based algorrthur Tree 1 30 30 A Treebased algorithm Tree 2 20 Treebased algorithm 20 39 39 Treebased algorithm Tree 3 9K I Greedy algorithm 45 Greedy algorithm D 39 10 Random 10 V Random 7 Hot Spot V 7 Hot Spot 0 0 l 15 2 25 3 l 2 3 4 5 6 7 8 9 Relative Performance Relative performance In a treestructure network greedy treebased gt hot spot gt random The paper says greedy is slightly better why In an arbitrary network greedy gt hotpot gt tree gt random Server Placement in Real World Assumptions hold true Tme Each client uses a single replica surrogate server Policy issues How to Redirect URL rewriting Origin server redirects clients to different surrogate servers by rewriting the page s URL links o Dynamic 0 Static Bottleneck Domain Name System DNS redirection DNS server direct requests to CDN Select a CDN From a customer s point of view which CDN to choose Cache hit ratio Saved bandwidth Surrogate server utilization Reliability Outline Introduction to CDN gtAn Industry Example Akamai Research Example CDN over Mobile Networks Conclusion Overview of Akamai lt3 Launched in 1999 Over 12000 servers in 62 countries Serves Yahool Apple AOL How Akamai works Domain Name System DNS redirection Normal DNS Working Process com XXAXXXXXX edu XXXXXX xx org j Root DNS Servers Top Level Domain Servers intelcom xxxxxxxx yahoocom xxxxxxm39lt quotquotquotquotquot aolc0m xxxxxxxx Authoritative DNS Servers newsyahoocom xxxxxxxx sportsyahoocom xxuxxxx gamesyahoocom xxxxxxxx local DNS server npul tmyallthCDm How DNS Redirection Works erodf 39 XXAXXXXXX edu XXXXXX xx org 39 Root DNS Servers Top Level Domain Servers inte1com xxxxxxxx yahoocom xxxxxxm39lt quotquotquotquotquot aolc0m xxxxxxxx Authoritative DNS Servers newsyahoocom sportsyahoocom K i V gamesyahoocom DNS ow ned or administrated b Akumai Looking For a proper Akamai surrogate server An Akanmi surrogate Server How DNS Redirection Works cont What Akamai does Manage customers DNS server Pretend to be a normal DNS server But more complex inside o Probing o Selecting o Load balancing Example visit Yahoo via Akamai Selecting Criteria Server must be able to satisfy the request eg can handle streaming media Has the content Server health Server load Network condition Packet loss rate Bandwidth Client location Different Types of Content Static content Lifetimes Special features Dynamic content ESI break a dynamic page into fragments Assemble dynamic pages at surrogate servers Streaming media Deliver packets without significant delay or jitter 32 Content unreachable Split the TCP connection into two separate connections Outline Introduction to CDN An Industry Example Akamai gtA Research Example CDN over Mobile Networks Conclusion A Research Example CDN over MANET 3 In a more general sense CDN refers to any overlay network built for the purpose of facilitating content delivery Background Pervasive computing ubiquitous computing 0 Goal make computers work in a more intelligent way Decrease users intended input 0 Representative applications Examples 3 S Chen et al Application based Distance Measurement for Context Retrieval in Ubiquitous Computing MobiQuitous 2007 Philadelphia US Hardware Environment Sensors computers smart phones and PDAs Both fixed and mobile nodes Each node may serve as data producer and data consumer We want to improve the data retrieval performance however it s impossible to store replicas on every node Limited storage Limited energy Communication costs Context Clustering Different types of data contexts Light sound temperature humidity user s schedule location Logical distance between contexts Which contexts are often used queried by applications simultaneously q sjlj cosS T Zr J1 F1 DST sinST 11 cos2ST Replica Placement If the logical distance between two types of contexts is lower than a threshold they cache each other or shortcuts are built between t em Index 39139 Cl Room507 temp 1quot C2 Jan locateln Iquot Contexts RoomSIO temp 12 Tom locatelnRoomquot Jan locatelnRoom5quot 9 Shortcuts pe er Cl peer4 peer6 C2 peer7peer12 Outline Introduction to CDN An Industry Example Akamai Research Example CDN over Mobile Networks gt Conclusion Conclusion CDN is a overlay network which aims at efficiently delivering content Open issues CDN on P2P networks mobile networks Authentication security issues Community Structure and Beyond Elizabeth A Leicht MAE 298 April 9 2009 Why do we care about community structure 56m 292me 1 l M nljw Vl39lr m X I wwzIM Ev a y a p 1 i i a3 IT 1 Vv M u on r Q39A7 3an Ay II V k Discussion Outline 0 Overview of past work on community structure 0 How to determine the best number of communities 0 Fast linear algebra based method 0 Bringing in statistics A Brief History of Methods 0 Spectral methods graph partitioning problems 0 A well known example is spectral bisection which uses the graph network Laplacian Lij Sij 1 Aij 0 In the special case of a network having only two communities Fiedler proposed a method for identifying the the members nodes A Brief History of Methods 0 Hierarchical clustering groups nodes into communities such that nodes within a community are similar to each other in some sense widely used in sociology 0 Technique 1 calculate a weight Wijfor every pair of nodes in the network 2 then take the n nodes with no edges between them an add edges between pairs one by one in order of their weights from strongest to weakest 0 Many ways exist for calculating the WM values 0 The entire process is frequently represented as a dendrogram a visualization of the vertices coalescing into communities A Brief History of Methods IIIIIIIIIIIIIIIIIIIII GiN Algorithm 0 GirvanNewman Algorithm a divisive method for determining community structure that focuses on the beMeenness of edges 0 Edge betweenness the number of shortest paths between pairs of vertices that run along an edge 0 Removing edges of high etweenness breaks up the connected network into communities Girwn and M E J Newman Community structure ii i sociai arid bioiogicai networksquot Pros Nari Acad Sci USA 99 782177826 2002 m w P Algorithm Caicuiate the oetweehhess tor aii edges in the network Remove the edge With the highest oetweehhess Recaicuiate oetweehhess tor aii edges treeted by the remova Repeat irom steps 2 ui itii ho edges remaii i number of inter communin edges Mn f39rncliun of veniurs classified concclJ l llll GN Algorithm GN Algorithm The classic Karate Club example b Modularity MEJ Newman and M Girvan Finding and evaluating community structure in networks Phys Rev E69 026113 2004 0 Introduced by Newman and Girvan to quantify which division of a network into communitiesgroups was the best 0 Related to Newman s work on assortativity in networks Mixing patterns in networks Phys Rev E 67 026126 2003 0 Modularity the fraction of edges falling within communities minus the expected fraction of such edges 67 the fraction of all edges in the network that link vertices in community 1 to vertices in community or Z em the fraction of edges that connect to vertices in j community 1 Q Em w Ire llele Modularity MEJ Newman and M Girvan Finding and evaluating community structure in networks Phys Rev E69 026113 2004 lamina gs Li 533 mm mopuu Again the Karate Club Modularity modulan39ty O 0 0 We love to study ourselves an wt 1 b A New New Approach a Newman later returned to the subject of oommunity structure and modularity with a newinew approach M E J Newman Pmc Acad Sci USA 103 8577 8582 20 6 0 J Modularity maximization was the leading tool for determining optimal comrrunity structure 7 Simulated annealing had been shown to be very suocessful but slow Natl Calculating Modularity Rewrite modularity using the adjacency matrix A 1 if there is an edge from j to i 1 0 otherwise 39 Pij the expected number of edges from j to i ci 2 the community to which 1 belongs How do we determine the expected number of edges between two vertices kikj PM 2m Division of a Network into Two Communities 31 1 3139 71 1 I knkf 391quot U 41 39 2 B 4m 2m x 1 41725 s U i A 5ij 5313 1 Wk lt s V121 ugui With a u s 4 H i r quot q i J E alufB E aju illI S I39J39g j 21 t Again with the Karate Club IaS IOH B t 90 h Edge D COmmuni ies W o V43 Qa 39glgnwp 39 q4 I quotm 7 1A lt v 41 39O 9 391 quot 4I V A 7 mv u IaS Ion B t 90 IGS WI Commun th Edge D 0W9 w v9 A m I s I I M Edge Direction Bias in Real Networks Pennsylvania State Northwestern 1w 4m IRVAO avaMVI v lt Wisconsin s 9 I Edge Direction Bias in Real Networks Pennsylvania State Northwestern A s lt7 Mlchlgan State Q Qer j gm W1 s C 0n s1n II L Purdue I g Exploratory Analysis of Structure in Networks Previously we identified communities in networks because we specifically sought a method to detect modules in networks Reliance on specific measures of network structure where we are required to know the type of structure for which we are looking in advance can be limiting We turn to probabilistic techniques and the Expectation Maximization EM Algorithm to identify general patterns of connection between vertices The Method There are three types of quantities in this method of approach 1 Observed data the actual edges falling between pairs of vertices in a network A 2 Missing data we assume that the vertices divide into c groups We denote the group to which vertex 1 belongs as 91 and set of all missing data as 9 3 Model parameters they describe the patterns of vertices in different groups 9 n e the probability that there exists an edge from a vertex in group 1 to a vertex i 7tr the probability of a vertex belonging to group 1 C TL Z 7 1 Z 6 1 r21 i1 A Likelihood Problem The likelihood of the data given the model is PrA7 9 7T7 Prg7T7 6 where PrAg 7 e H 93 and Prg7 e Hngj ii 139 Frequently one works not with the likelihood itself but with the loglikelihood L 1n PrA g7t 9 Z In gj H9313 i Dealing with the Missing Data We cannot directly obsene g It is however possible to calculate an expected value for the loglikelihood over all possible values of g C E Z Z PTgA97 Ei1n7tgjZAij1negjai 91 gnzl i1 1 ZZXXOM r1j1 1n 7Tr I Z Ai 1D Gri i1 where P A e r eAji quPrlgjrlAmel 1 79 7 7 l 7 H1 m PrA7 E 9 8 718 Hi Sign The EM Algorithm Initialize model parameters 9 l39 with random values Find the probability a given vertex j is a member of group 1 Estep A r Hi Grin A 3 7 8 Hi est Maximize the model parameters llstep 1 r 7T1 Z ZJ Uq n i j kiqu qu lterate until convergence Arm gtQqumzj 2220 1 M nljw Vl39lr m A 394 wwzIM Ev L a A w 1 i i a3 IT 10 0156 v QMad39WfJ M u n by 3A 4 lt 4 A 3 x 39 Ay II V k Example Karate Club 33 s 1 gt lf A A 1 9 F y w Example Word Network Example AssortativeDissassortative Network lt assortative disassortative gt 1 U1 6 8 05 3 U H this paper I I max modularity A A min modularity 0 A I I 01 probability ratio pout pin Example AddHeaIth I Black 0 White I V Hispanic 0 Unknown 39 J O Other 39 Example A Keystone Network Example A Keystone Network I I I I I I I I I I I 9 quotI I 9 n I n I n 3 1 b m onquot lWi ll I I IIIIIIII II no I m n a 3 1 m quot3 n co m n o 0D lllllllll Big Ten Results with the EM Algorithm Vertex size based on probability of being beaten by teams assigned to group 1 qjl 0 05 1 Vertex shading based on probability of being assigned to group 1 Example The Big Ten Conference

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "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."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.