## Index

abundance problems (in Web searches) 352

activities, high-risk 516

ad quality 388, 404–406

in keyword-based advertising 633–635

role of 405

Adamic, Lada 10

adjacency matrix vector 368, 374

adoption(s)

awareness vs. 509–510

cascade of 503–504, 525–526, 534

of communication technologies 498–499

complete cascade of 503–504, 507–509, 514, 518–519, 522, 526

of hybrid seed corn 498

initial adopters 501–510, 512–514, 518–521, 524–529, 532–534

of new drugs by doctors 498

of two behaviors, interface between 520–521

advertising

auction price-setting 387

as a matching market 388–391

paying per click 386–387

quality issues 404–406

and search behavior 385–386

affiliation networks 84–88, 104–105, 349

agenda setting 652–653, 657

agricultural goods markets 278, 280–282, 297

Akerlof, George 631–632

algorithmic Web searches 386

all-pay auctions 232–233

equilibrium bidding in 241–242

AltaVista search engine 344–345

alternating breadth-first search 266–268, 270

alternating paths 264–265

alternatives (in voting system) 646–647

Amazon 353–358, 479, 486, 489, 646

Anderson, Chris 486, 489

Anderson, Lisa R. 427–430

Apple Macintosh 505, 517

approximate structural balance 113, 127–132

Aristotle 78

ARPANET (Advanced Research Projects Agency Network) 22–23, 25, 30–31

Arrow, Kenneth 17, 658

Arrow's Impossibility Theorem 17, 657–658, 673–678

*See also *Independence of Irrelevant Alternatives, voting systems

Arthur, Brian 453, 465, 470, 472

“As We May Think” (Vannevar) 339

ascending bid auctions (English auctions) 226

relation to matching markets 261–262

vs. second-price auctions 228–229

asexual reproduction 588

ask (in stock transaction) 279

associative memory 339

asymmetric information 608, 622–629, 634

in health insurance markets 629–630

in labor markets 627–628

in the stock market 630–631

auctions 8–9, 12, 15

all-pay auctions 232–233, 241–242

appropriateness determination 226–228

ascending bid auctions 228–229, 262, 275

common values (for items) 227–228

descending bid auctions 226, 228

first-price auctions 226, 228, 232–235, 238–241

format variations/relationships 228–229

generalized second-price auctions 387

independent private values (for items) 227

oral bid auctions 226

potential energy of 261

procurement auctions 277

reserve prices 240–241

revenue equivalence 239–240

second-price sealed-bid auctions 226, 229–232, 277, 290–291

setting prices through 387

single-item auctions 258, 261–262, 275

types of 225–233, 258, 261–262, 275

Vickrey auctions 226, 229–232, 277, 290–291

winner's curse 233–234

*See also *eBay, second-price sealed-bid auctions

audience 479, 485, 486

audience size 460–469, 471–473, 475–476

augmenting paths 266–267

authorities (in Web searches) 356–358, 364, 368–374

Authority Update Rule 356–358, 370

authority vectors 371, 374

autonomous system 38

average distance (over pairs of nodes) 33, 40–41

Balance Theorem (Harary) 111–112, 117–118

balanced division (of a network) 123

balanced outcomes 317–320

application/interpretations of 319–320

defined 318–319

balanced triangle formations 109

bargaining

formulation as a dynamic game 321–322

Nash bargaining solution 310–312, 318–320, 322, 324–326

outside options in bargaining 310–312, 318–324, 326

role of social status in 312

two-period version of 323–324

bargaining game 321–325

Barnes, John 23

Basic PageRank Update Rule 359–360, 374, 377

basic reproductive number 570–572, 574–575, 578–579, 591, 592–593

Bayes' rule 430–434

and events 430–434

in the herding experiment 434–436

and sample space 430–431

spam filtering and 433–434

taxi cab example of 432–433

Bayesian learning 635–638

behavior of networks 4–6

behavior(s)

aggregate behavior 15–17

cascading behavior 501–505

connectedness and 11–15

and game theory 7, 8–9

information conveyed by 13

multiple, coexistence of 501–505, 523

networked coordination game 499–500

threshold for adoption of 501–505

bell curve 480

Berkowitz, Lawrence 426

Berners-Lee, Tim 334, 339

best friends 303, 305

best-response dynamics 213, 215–217

best responses (in games) 146–149

Betamax technology 464

betting

expected utility 611–613

inverse odds 617, 619, 640–642

logarithmic utility function 612–615, 617, 641–642

risks 610–611, 617, 624, 629–630

utility function 611–615, 617, 624

*See also *expected utility, horse races, wisdom of crowds

betting markets 608–609, 619, 621, 639

*See also *prediction markets

betting your beliefs 613

betweenness 66–67

of edges 67, 68, 71, 74

of nodes 67, 74

as a source of power 303, 307

values computation 71–74

Bharat, Krishna 364

Bickman, Leonard 426

bid (in stock transaction) 279

bid-ask spread 297

bilingual coordination game 524

bilinguality 523–524, 530

Bing (Microsoft) search engine 363

biological contagion 14, 568

biological epidemics 14

biological networks 38

bipartite graphs 84–85, 103–104, 126, 250–254, 261–265, 267–276, 309–310

bipartite matching problem 250, 253–254

as a special case of optimal assignment 254

blockbusters 486, 487

blocking clusters 514

blogs 2, 4*f*, 37, 334, 341–342, 345–346

LiveJournal 92–93, 546, 548*f*

microblogs 57, 348

PageRank measure and 359

politics-based 4, 10

Twitter 348

boards of directors 36, 86, 103

body size game 190–195

bonding capital 62

Borda, Jean-Charles de 654

Borda Count 654–657, 678–679

bottlenecks 293–294, 468–469

boundary-spanning links 59*f*

Bourdieu, Pierre 61

bow-tie structure of the Web 344–347, 350

downstream nodes 346–347

PageRank and 361

tendrils 346–347

upstream nodes 345, 347

Braess, Dietrich 210

Braess's Paradox 8, 207, 209–212, 249, 470

branching process 569–573, 575, 578–579, 585, 590–596

breadth-first search technique 29–30, 30*f*, 31*f*, 119, 124–127, 265, 542

alternating 266–268, 270

breadth-first search layers 72–73

breakdown probability 322–325

bridges 46–47

bridging capital 61–62

Broder, Andrei 344–345

brokerage 62

brokers 31, 277–278

*Brown v. Board of Education* 367

*Brown v. Mississippi* 366

browser (Web browser) 334

bubonic plague 567

Burt, Ron 58, 60, 62

Bush, Vannevar 339

buyer-seller networks 257, 289*f*, 309–310

buyers 9, 37, 249, 255, 257, 261, 275, 277–300, 411–413

call graphs 37

cap-and-trade systems 685

capital, types of 61–62

Cartwright, Dorwin 108, 117, 121

Cartwright-Harary Theorem 108, 117, 121

cascade capacity 518–522

cascade of adoptions 503–504, 525–526, 534

cascading behavior 501–505

cascading extinctions 38

Central Limit Theorem 480–482, 484

centrality measure 303, 307

Characterization of Weakly Balanced Networks 117–118

Chicago Wine Company 225

Christie's auction house 225

citation analysis 38, 366

citation networks 38, 336–337, 366

citations 23, 336–337, 481

to scientific papers 481

U.S. Supreme Court 366–368

cities, populations of 484

Civil Rights Act (1964) 368

clickthrough data 364

clickthrough rates 388

ad quality and 405

assumption of fixed 404

clique (complete graph) 108–109

close-friend network 564

“closed communities” of individuals 14

closure 58–62

*See also *triadic closure

closure processes 86–87

clustering coefficient (in triadic closure) 44–45

clustering exponent 543–544

clusters 4*f*, 8, 10, 506–509

blocking clusters 514

cohesion of 506

as obstacles to cascades 507–509

coalescent processes (analysis) 596–602

Coase Theorem 681–682, 685, 688

coauthorships 35, 36, 38

coevolution of networks 86

coexistence of multiple behaviors 501–505

Coleman, James 61–62, 498

collaboration graphs 25, 26*f*, 27, 34–36

collective action 514–516

common knowledge 144, 516–517

communication network 23

*See also *ARPANET (Advanced Research Projects Agency Network)

communication technologies, adoption of 498–499

compatibility

and bilinguality 530

diffusion of innovations and 499

role of, in cascades 522–531

complete cascade 503–504, 507–509, 514, 518–519, 522, 526

complete graph (clique) 108–109

components 25–27

computer viruses 568

concurrency 584–585

conditional probability (and Bayes' rule) 430–432

Condorcet, Marquis de 650, 665

Condorcet Jury Theorem 664–665, 668–669, 671–673

Condorcet paradox 649–653, 658–659, 661

conformity 12–13, 425–427

connected components (of graphs) 26, 341

connected graph 25

connectedness 1–2, 4–11, 14, 17

constricted sets 251–253, 259–260, 262–263

augmented paths and 266–268

Matching Theorem and 268

contact network (of an epidemic) 567–585

contacts

local 554–556, 563

long-range 542, 554–556, 559–563

contagion

biological contagion 14, 568

random effects in 568

social contagion 14–15, 83, 568–569

contexts (of a network) 43, 47, 49, 77

convergence (of hub-authority computation) 372

cooperative game theory 320

coordination games 151–154, 499–501

copying models 483, 486

copyright law 690–691

core (of a network) 553

core-periphery structures 552–554

core solution 320

cost per click advertising 386–387

counting edges 129

counting triangles 129

creativity (as a consequence of structural holes) 60

critical point 457, 463, 625

cross-references 337

crossing pair (of bid and ask prices) 291

cultural capital 61

cumulative distribution function 238

cycles 25

dark pools 279–280

Davis, James 115–116

decentralization (of markets) 249, 255

decentralized search 541–546

core-periphery structures/difficulties in 552–554

delivery time of 542

modeling the process of 543–546

decision making

Bayes' rule and 635

disease and 568

group decision making 645–646

by groups (voting) 645–646

rich-get-richer models and 482

sequential 440–442

in a social network 498–499

under uncertainty 430–434

Del.icio.us 91

delinquent behavior 82

demand function 451

dependence (as a source of power) 303

dependency networks 24*f*

descending bid auctions (Dutch auctions) 226

vs. first-price auctions 228

deterministic approximation 491–493

diameters (of graphs) 40–41

Diamond, Jared 28

dictatorship (voting system) 658, 674–675

differential equations 237–238, 241, 490–492

diffusion

homophily as barrier to 506

of ideas and behaviors 568–569, 584

of information 537, 584

of innovations 498–499

modeling of through a network 499–505

role of weak ties, thresholds, and 509–514

of technologies 14

Digital Millennium Copyright Act (1998) 691

direct-benefit effects 426–427, 449, 498

Direct Edge 278

directed edges 21, 24*f*, 37–38

directed graphs 21, 22*f*, 114, 207, 211, 219–222, 340–344

giant strongly connected components 345, 349

strongly connected components 342–344

of Web pages 350*f*

disease 28–29, 32

distance (between nodes) 29–31, 33–36

distant-friend network 564

distrust 114–115

DNA (deoxyribonucleic acid) 586

*See also *mitochondrial DNA

dominant strategy (in games) 146–149

dominated strategy 167–173

iterated deletion of 170–172

weakly dominated 172–173

download statistics 485

drugs

doctors' adoption of 498

usage of 82–83

Dutch auctions (descending bid auctions) 226

dynamic games 142, 173–179, 320–322

dynamics of networks 4–6

e-mail networks 2, 92, 348, 551, 553*f*

eBay 225, 229, 622, 632–633

economic capital 61

economic transactions 37–38

edges 21, 23–25, 28–29, 34, 37–39

betweenness of 67, 68, 71, 74

counting 129

embeddedness of 58–59

formation of via triadic closure 45*f*, 47*f*

friendships and formation of 89–90

matching edges 263–268

nonmatching edges 263, 265, 266, 268

of social networks 48*f*

“social value” on 305

strong/weak ties division of 49

eigenvalues 368, 371–376

eigenvectors 368, 371–372, 374–376

El Farol Bar problem 470–476

repeated 474–476

two-player 473–474

elections 4*f*, 10, 16

elimination tournament 651–653, 678

embeddedness 58–59

Emerson, Richard 302

employment 43

encyclopedias 337, 338*f*, 339, 348–349

endogenous events 607–608, 622

energy minimization 113

English auctions (ascending bid auctions) 226, 262, 275

epidemics 14, 567–604

branching process 569–572, 591–596

coalescent processes (analysis) 596–602

contact network of 567

infectious state 572–573, 576–577

livestock populations during 567

Mitochondrial Eve and 586–587

networks that transmit them 567–568, 567–569

oscillation of 579–582

plant populations during 568

public health measures 571

random effects (in contagion) 568–569

removed state 572

SIR model 572–576

SIRS epidemic model 580–581

SIS model 576–578

susceptible state 572, 576–577

synchronization of 578–582

transient contacts/dangers of concurrency 582–585

Epinions (products rating site) 113–114

equidependent outcome 311

equilibrium odds 616

equilibrium of hub/authority scores 358

equilibrium quantity (of a good) 451–453

equilibrium traffic 207–209

equiresistance 320

Erdös, Paul 35

Erdös number 35

essential edge 296–297

evolutionarily stable mixed strategies 199–203

evolutionarily stable strategies 191–195

evolutionary arms races 194–195

evolutionary biology 189

evolutionary game theory 189–203

evolutionary stability

interpretation in body-size game 193–194

and Nash equilibrium 197–201

exchange theory 304

exclusion (as a source of power) 303, 305–306

exogenous events 607–608, 610, 618

expected utility 611–613

expected value 80–81, 158, 239, 326, 556–557, 560, 591, 592–593, 600–601, 611–612

exponential growth 539*f*

extensive form game 173–179

externalities 449–450

and the Coase theorem 681–682

negative externalities 450, 470–472

and nonoptimal allocations 682–684

positive externalities 449–450, 470–472, 686

f-majority rule 672

Facebook 6, 12, 38, 348

News Feed service 54, 57

strong/weak ties on 57–58

tie strength on 54–57

fashion leaders 464

fictitious slots (in advertising auctions) 390, 399, 402

Fidelity 279

Fifth Amendment 366, 367*f*

finite-horizon game 322, 324–325

first-price auctions 226, 228, 232–235, 238–241

descending bid auctions vs. 228

equilibrium bidding in 234–235

fitness 139, 189–195, 197, 200, 202–203

five-node path (in network exchange theory) 307, 316

Flickr 5–6, 13, 91, 348–349

flow of goods 282–284, 288, 290*f*, 292–295, 297–300

flow values computation 73–74

focal closure 87, 91–94

focal point (in games) 152

foci (social foci) 84–88, 91–94, 549–551

food webs 38

forecasting rule 475–476

four-node path (in network exchange theory) 306–310, 312, 314, 317, 319–320, 329

free association 338

Freedom Summer 511

Freeman, Linton 67

friendships

analysis at Facebook 54

edge formation and 89–90

geographic data on 546

homophily and 78–81

interpersonal/structural interpretations of 43

rank-based 546–549

selection and 81

suicide and 45–46

triadic closure and 45–46

games/game theory 7, 8–9, 12

assumptions in 142–143

bargaining game 321–325

basic ingredients 141–142

best responses/dominant strategies 146–149

bilingual coordination game 524

body-size game 190–195

cooperative game theory 320

coordination games 151–154

defined/described 139–142

dominant strategies 147–149

dominated strategies 167–173

dynamic games 173–179

extensive form game 173–179

finite-horizon game 322, 324–325

focal points in 152

infinite-horizon game 322, 324–325

iterated deletion of dominated strategies 170–171

iterated deletion of strictly dominated strategies 170–171

mixed strategies in 161–165, 199–203

multiplayer games 167

networked coordination game 499–501

normal form game 173, 175–179

online games 36, 535–536

pure strategies 157–162, 164, 177, 179–187

reasoning about behavior in 142–146

Stag Hunt game 153–154, 172, 197–198

strategies/payoff matrix 142

strictly dominant strategy 143, 147–149

strictly dominated strategies 168–173

symmetric game 196–198, 200, 205

unbalanced coordination game 152

virus game 195, 203

weakly dominated strategies 172–173

*See also *Hawk-Dove game, Nash equilibrium, Prisoner's Dilemma game

Garfield, Eugene 366

gatekeepers 40, 60

Gaussian distribution 480, 487

genealogical networks 588

generalized second-price auction (GSP) 387, 398–401

Google's adaptation of 405

multiple equilibria in 400

nonoptimal equilibria in 400

socially optimal Nash equilibrium for 403–404

genetic duplication 484

genetic inheritance 568, 585–586

*See also *lineages, Mitochondrial Eve, single-parent ancestry

geography 538, 540, 542–543, 546, 549–550, 553–554

giant components 27–29, 46, 52, 333

giant strongly connected components (SCC) in directed graphs 345, 349

Girvan-Newman Method (of graph partitioning) 66–70, 74

Glance, Natalie 10

global friendship networks 27–36, 341

global name-recognition network 341

Gmail 348

Goldman Sachs Sigma-X 279

gonorrhea epidemic 582

Google (company) 225, 385

Google search engine 10–11, 345, 349, 351–352, 363–364, 405, 489

Google Trends 5*f*

governments, repressive 514–515

Granovetter, Mark 43, 46, 47–48, 49, 51, 52, 59, 337

graph partitioning 63

agglomerative methods of 65–66

betweenness and 66–67

divisive methods of 65–66

Girvan-Newman Method 67–70, 74

graphs (graph theory) 7–8

breadth-first search 28–29

collaboration graphs 25, 26*f*, 27, 34–36

complete graph (clique) 108–109

components 25–27

connected components 26, 341

connected graph 25

cycles 25

directed graph 114, 207, 211, 219–222

domains of appearance 22–23

edges 21, 23–25, 28–29, 34, 37–39

giant components 27–29

information linkage graphs 37–38

of Microsoft Instant Messenger 33–37

minimum-cut approach 70

as models of networks 21–23

nodes 21, 22–31, 22*f*, 33–35, 37–39

paths 23, 25

preferred-seller graph 257, 270, 275, 276, 390

spectral analysis of 368

structural holes in 60–62, 67, 303, 511

triangle formations in 47

undirected graph 21

who-talks-to-whom graphs 37

*See also *bipartite graphs

grid network 540–541, 561–562

group decision making 645–646

group preferences 649–651, 661, 679

group ranking 647, 649–652, 654–658, 661–663, 673–679

Guare, John 31, 35

*Guns, Germs, and Steel* (Diamond) 28

Hall, Phillip 251

Harary, Frank 108, 111–112, 117–118, 121

Hardin, Garrett 685–689

harm-done-to-others principle (VCG procedure) 395

Harry Potter 485

Hawk-Dove game 154–156, 165, 199–203, 473–474

Heider, Fritz 108

herding 425–427, 434–440, 442

herding experiment 427–430, 434–436

heterogeneous thresholds 512–514

high-risk activities 516

Hilltop link analysis method 364

HIV/AIDS epidemic 582–584

Holt, Charles A. 427–430

homophily 77–83

as barrier to diffusion 506

editing of Wikipedia and 94–95

and friendships 78–81

inverse homophily 81

measurement of 79–81

mechanisms underlying 81–83

and selection 83

and Watts-Strogatz model 539–540

homophily test 80

horse races 609–615, 617–620, 624, 635–636

and aggregate diverse opinions 609

and state prices 616–621

hub-authority computations 357, 360, 368–369, 370–372, 375–376, 378–380, 382

hub-authority vectors 368

Hub Update Rule 357–358, 369

hub vectors 371–374

hubs (in Web searches) 356–358, 364, 368–374

human capital 61

hybrid seed corn, adoption of 498

hypertext 334–337, 339–340

impact factor (for journals) 366

implicit perfect competition 289–290, 295

Impossibility Theorem (Arrow) 17

in-links 353–354, 357, 359, 366, 382, 479–480, 482, 490, 493

Independence of Irrelevant Alternatives (IIA) 657, 673

independent private values (for auction items) 227

indifference 160, 164, 201, 284, 287–288, 291, 323

infinite grid 519

infinite-horizon game 322, 324–325

infinite networks 518, 524

infinite path 518–520, 524, 526–530

influence weight (for journals) 366

influenceable people 513

influential people 513

influenza epidemic 567

information

asymmetric information 608, 622–629, 634

benefits of structural holes to 60

in network exchange theory experiments 305

symmetric information 624

transmission across local bridges 46–47, 510–511

information aggregation 663–668

insincere voting for 665–668

voting as a form of 663–665

information cascades 13–14, 425–447

cascade model 436–440

expert opinions and 446–447

fragility of 430

lessons from 442–444

marketing and 444

nonoptimal outcomes in 429

power laws and 485–486

probability of occurrence 440–442

sequential voting relation to 672–673

*The Wisdom of Crowds* and 443

information linkage graphs 37–38

information networks 10–12, 23, 58, 70, 333, 335–341

information retrieval 351–353, 365

informational effects 12*f*, 426–427, 449, 498–499

initial adopters 501–510, 512–514, 518–521, 524–529, 532–534

innovation

compatibility of 499

complexity of 499

diffusion of 498–499

observability of 499

relative advantage of 499

trialability of 499

insincere voting 665–668

instability

in network exchange 315–317

structural balance and 109

and tipping points 456–459

instant messaging 33–37, 304–305, 312–313, 531

institutions

and aggregate behavior 15–17

as mechanisms for achieving common knowledge 516–517

intellectual property 681, 688–690

intermediaries 277–280

international relations 113

Internet 22–23, 24*f*, 38, 207, 333–334, 339

auction sites 225

multi-level network structure of 38

network structure of 22*f*, 38

*See also *ARPANET, hypertext, search engines, World Wide Web

Internet Movie Database (IMDB) 35

intrinsic value 226

invaders 192, 197, 200–201

invades 192, 200–202

inverse demand function 451

inverse homophily 81

inverse odds (in betting) 617, 619, 640–642

Investment Technologies Group (ITG) 278, 279

Iowa Electronic Markets 608

Iraq 517

iterated deletion 170–172

job-seeking 43

jury decisions 668–672

karate club 2, 7, 8*f*, 64, 88

kernel solution 320

Kevin Bacon game 35

keyword-based advertising 385

König, Denes 251

labor markets

asymmetric information in 627–628

education as signal in 631–632

equilibria in 629

signaling quality in 631–632

Law of Large Numbers 637

Lazarsfeld, Paul 78

legal citations 366–368

lemons, markets for 623–627

lengths (of a path) 29, 31, 32*f*, 33*f*

limit orders 278–279

lineages 586, 588*f*, 589–591, 596–602

linearity of expectation 557, 591, 600–601

link analysis (in Web search) 363–365

of U.S. Supreme Court citations 366–368

using hubs and authorities 353–358

Web search application of 363–366

LinkedIn 91

links 1–2, 4, 7, 9, 10–11

long-range 543, 549, 555, 557, 562, 563, 580–582

random links 540*f*, 541*f*, 543–544, 547

tracking formation of in online data 88–96

list-finding heuristic (in Web searches) 353–354

LiveJournal (blog) 92–93, 546, 548*f*

livestock populations (during epidemics) 567–568, 603

local bridges 46–47, 52

information transmission across 46–47, 510–511

and weak ties 49–51

local contacts 554–556, 563

local gatekeepers 40

log odds ratio 637

logarithmic utility function (in betting) 612–615, 617, 641–642

long-range contacts 542, 554–556, 559–563

long-range links 543, 549, 555, 557, 562, 563, 580–582

the Long Tail 13, 349, 486–489

low odds (in betting) 610

maintained relationships 54, 56*f*

majority rule system 649–653, 655–658, 661, 662–663, 665, 667

market-clearing prices 256–260, 262, 270, 272–276

construction of 258–261

defined 256–257

obtaining 390–391

optimality of 257–258

market makers 277

market order 279

market prices 451–452, 470

markets 249

for agricultural goods 278, 280–282, 297

as an artificially intelligent Bayesian agent 635–638

with endogenous events 622–623

failure of 623, 625–627

for insurance 629–632

for keywords 389

labor markets 627–629

for lemons 623–627

prediction markets 608–609, 619–621, 635, 641

used-car markets 622–624, 628, 630–632, 634, 642–643

wealth dynamics in 635–641

matching 304, 314–317, 319

matching edges 263–268

matching markets 249–276

bipartite graphs and 250–254, 261–265, 267–276

bipartite matching problem 250, 253–254

buyers 249, 255

constricted sets 251–253

decentralization (of markets) 249, 255

for keywords 388–391

market-clearing prices 256–260

maximum matching 263, 268–270

neighbor sets 251

optimal assignments 253–254

payoffs and prices 255–256

potential energy 260–261

potential of a buyer 261, 275

potential of a seller 261

preferred-seller graph 257, 270, 275, 276

preferred sellers 255–262

sellers 249, 255

truthful bidding in 391–395

valuations 253–254, 255

*See also *market-clearing prices, perfect matchings, price

Matching Theorem 252–253, 262–270

maternal lineage 586, 589

matrix-vector multiplications 368

maximum matching 263, 268–270

Maynard Smith, John 189

mean (of a normal distribution) 480

measles epidemic 567, 579, 582

median voter 663

Median Voter Theorem 658–663

membership closure 87, 91–94

Memex 339

Merton, Robert 78

meta-search 646

metabolic networks 39

microblogging 57, 348

*See also *Twitter

Microsoft (corporation) 225

Microsoft Instant Messenger 33–37

middlemen (traders) 277–278, 280

Mihaila, George 364

Milgram, Stanley 31–35, 426, 537–538, 541–543, 545, 549, 551–553, 555–556

minimum cut (in graphs) 70

minimum market-clearing prices 409–418

*Miranda v. Arizona* (1966) 366–367

mitochondrial DNA 586–588, 590

Mitochondrial Eve 586–587

mixed strategies (in games) 161–165, 199–203

monopoly (of buyers and sellers) 286–287, 296*f*

Morrell & Company 225

most recent common ancestor 589*f*, 590, 597, 599, 602

multiple equilibria 301

coordination game 151–154

Hawk-Dove game 154–156, 165, 199–203, 473–474

network effects and 456

myopic search 555–561

MySpace.com 12, 348

NASDAQ-OMX 278

Nash, John 150, 156, 160, 162, 320

Nash bargaining solution 310–312, 318–320, 322, 324–326

Nash equilibrium 149–162, 164–168, 170–173, 177, 179–187

and Braess's paradox 209–212

in the El Farol Bar problem 472–473

evolutionary stability and 197–201

for the generalized second-price auction 403–404

with mixed strategies 158–165

relationship between evolutionary and 197–199

in the traffic game 208–209

*See also *strict Nash equilibrium, subgame perfect Nash equilibrium

natural selection 194, 635, 641

navigational links (World Wide Web) 340

negative externalities 450, 470–472

negotiation 304–312, 310–312, 317, 320–324, 320–324.326, 326

neighbor sets 251

neighborhood overlap 52, 59, 94

neighbors 21, 97

Netflix 486, 489

network data sets 35–39

network effects 13, 449–478

adoption of technology and 449

and competition 464–465

consumer confidence and multiple equilibria with 456

dynamics of a market with 457–462

economy with 453–456, 459

economy without 450–453, 456

equilibria with 454–456

as externalities 449–450

market conditions and 469

marketing a product with 463–464

media-sharing site and 449

social networking site and 449

social optimality of market equilibrium with 464

social optimality of market equilibrium without 453

social optimality with 464

network evolution 43

network exchange experiments 304–309

balanced outcomes and 317–320

information in 305

matching market's relationship to 310

paths in 306–307, 312

stable outcomes and 314–317

unstable networks in 308–309

network exchange theory 249, 302

networks

aspects of 2–7

contact network (of an epidemic) 567–585

data sets 35–39

diffusion in 497–499

genealogical network 588

graphs as models of 21–23

grid network 540–541, 561–562

information network 10–12, 23, 58, 70, 333, 335–341

markets/strategic interaction in 9–10

modeling diffusion through 499–505

regions (divisions) of 63–64

ring network 555, 581

ripple effects from changes to 291–293

scales of resolution in 545–546

semantic network 338–339

sexual contact network 582

small-world contact network 580–582

structural balance defined for 109–110

time-expanded contact network 578, 579*f*

trade on 280–286, 297

tree network 574–575, 591–594, 597, 602

triangle formations in 44, 47, 60, 66–67

weakly balanced network 116–118

neural connections 38–39

neutral model (of inheritance) 588

New York Stock Exchange (NYSE) 278

niche products 486–489

nodes 21, 22–31, 37–39

average distance over pairs of 33, 40–41

clustering coefficient of 45

distance between 29–31, 33–36

gatekeepers 40

neighborhood overlap and 52

pivotal nodes 39–40

shortest paths between 29, 72–73

Strong Triadic Closure and 50*f*

supernodes 123–126

nonmatching edges 263, 265, 266, 268

nonrivalrous goods 688–690

nonsimple paths 25

normal distribution 480–482

normal form game 173, 175–179

normalizing (hub and authority scores) 357

nucleotides 590

obesity 83

occupations 537–538, 549, 553

odds (in betting) 610, 613–620, 639

equilibrium odds 616

inverse 617, 619, 640–642

one-exchange rule 304–307, 309, 314, 327–329

one-way communication 54, 55*f*

online games 36, 535–536

online ratings 114–115

operating systems (for computers) 505, 517

optimal assignments 253–254

optimality of market-clearing prices 258

oral bid auctions 226

order book 278

order statistics (in auctions) 239

O'Reilly, Tim 347–348

organic search results 386, 405–406

orthogonal eigenvectors 371–373, 376

oscillation (of epidemics) 579–582

outcomes

four-path node and 306–307

Nash bargaining solution and 311–312

stable outcomes 314–317

two-path node and 306

unpredictability of 308

outside options (in bargaining) 310–312, 318–324, 326

Overture 385

PageRank 358–364, 366

Basic PageRank Update Rule 359–360

bow-tie Web structure and 361

equilibrium values of 360

formulation using random walks 376–378

as Google component 363–364

random walk interpretation of 362–363

Scaled PageRank Update Rule 361–362

spectral analysis of 374–376

Palacios-Huerta, Ignacio 163–164

Pareto, Vilfredo 166

Pareto optimality 165–167

Pareto Principle 657

passive engagement 56–57

Patent and Trademark Office (U.S.) 691

patents 38, 337, 351–352, 690–691

paths 23

four-node path 306–310, 312, 314, 317, 319–320, 329

lengths of 29, 31, 32*f*, 33*f*

in network exchange theory experiments 306–307

nonsimple paths 25

short paths 31–32, 34, 303, 333, 338, 537–543, 549, 551–552

shortest paths 29, 39, 67–68, 71–74, 542, 556

and strong connectivity 341–343

three-node path 306, 312, 314, 316, 327, 329

two-node path 306, 310

payoff matrix (in games) 142, 152, 314, 321, 323–326

payoffs 8–9, 142, 255–258, 261, 309

peer pressure 82–83

percolation (and SIR epidemics) 575–576

perfect competition 286, 287–288

*See also *implicit perfect competition

perfect matchings 304

augmenting paths and 266–267

bipartite graphs and 251–252, 254, 262–263, 268–269

central “administrator” determination of 255

computation of 269–270

market clearing prices and 257–258

periphery (of a network) 553

Perron's Theorem 376

phone call networks 37, 51–52, 481

physical proximity 37–38

pivotal nodes 39–40

plant populations (during epidemics) 568

Plato 78

pluralistic ignorance 514–515

politics-based blogs 4, 10

polysemy 351

popularity 479–489, 493–494

of books 481, 485, 487–488

of Web pages 479, 484–486, 489

population density 546–547

population effects 12–13

populations 479, 482–483, 485

of cities 484

information cascades and 425–427, 485–486

Portes, Alejandro 61

positive externalities 449–450, 470–472, 686

Postal Service (U.S.) 546

posted prices 285–286

posterior probability 432, 439, 636–638

potential buyers 261, 275

potential energy 522

best-response dynamics vs. 213–215

of a buyer (at auctions) 261

relating to travel time for a single edge 217–218

of a seller (at auctions) 261

power

betweenness as source of 303

dependence as source of 303

exclusion as source of 303

satiation as source of 303

in social networks 301–303

weak power 307, 308, 310, 317, 320

power grids 38

power imbalances 312–314, 316, 317

power laws 481–487, 490–494, 548

and information cascades 485–486

via copying 486

via optimization 484

prediction markets 16, 608–609, 619–621, 635, 641

*See also *betting markets, horse races, odds

preference relation 647–651, 661

preferred-seller graph 257, 270, 275, 276, 390, 410–411

preferred sellers 255–262

Price, G. R. 189

prices 255–256, 258, 261, 285–286, 451–457, 460, 464–466, 468–471

*See also *market-clearing prices, market prices, posted prices, reservation prices, reserve prices, second-price sealed-bid auctions

principle of repeated improvement (in Web searches) 355–356

prior probability 431–434, 437–439, 636, 664–665, 669, 672

Prisoner's Dilemma game 144–147, 149, 154, 165–166, 193–195, 203, 210

private signal (cascade model) 437–438, 440–443, 445

probability

*See *posterior probability, prior probability

procurement auctions 225, 277

profile (in voting) 673–677

progress measure 213–215

property (properties)

intellectual property 681, 688–690

interpersonal, of social-network links 50

market-clearing property 407–409

Strong Triadic Closure property 47–49, 74

tie strength 50

Weak Structural Balance Property 116–117

property rights 681–692

externalities/Coase theorem and 681–685

intellectual property and 688–691

patents and 690–691

rivalrous/nonrivalrous goods and 688–690

“The Tragedy of the Commons” and 685–688

public health measures 571

pure strategies (in games) 157–162, 164, 177, 179–187

quarantines 571

random effects (in contagion) 568–569

random links 540*f*, 541*f*, 543–544, 547

random variables 591, 593, 600–601

random walks 362–363, 376–378

rank-based friendships 546–549

rationality 143

reachability (in a directed graph) 343

reciprocal (mutual) communication 54, 55*f*, 57

recommendation systems 349, 489

reduced graph 124

regions

from graph partitioning 63–64

tightly-knit 62–67, 69–70

relative entropy 638, 640

relevance feedback (in link analysis) 364

religious institutions 517

repressive governments 514–515

reputation score 632

reputation systems 349, 633

reservation prices 451–455, 464, 470–471, 476–477

reserve prices (in auctions) 240–241

revelation principle (in auction bidding) 235–236

revenue equivalence (in auctions) 239–240

revenues per click 388

rich-get-richer process 13

deterministic approximation of 490–493

models of 482–484

process analysis 490–493

unpredictability of 484–486

rigidity theory 24*f*

ring network 555, 581

ripple effects from changes to a network 291–293

risks (in betting) 610–611, 617, 624, 629–630

rivalrous goods 688–690

*Roe v. Wade* 367

Rogers, Everett 499

romantic relationships 28–29

root (of a tree) 569

Roughgarden-Tardos theorem 210–211, 212

Rubinstein, Ariel 320

sales rank 488

sample space 430–431

satiation (as a source of power) 303, 306

Scaled PageRank Update Rule 361–362, 375–377

scales of resolution (in a network) 545–546

scarcity problems (in Web searches) 352

Schelling, Thomas 96–98, 152–153, 182

Schelling segregation model 96–103

examples 99–100

homophily and 96–97

interpretations of 100–103

thresholds in 97–98

schisms (in social networks) 8

search engines 7, 10–11, 15

algorithmic Web searches 386

AltaVista search engine 344–345

Bing (Microsoft) 363

clickthrough rates/revenues per click 386

complex queries and 406–407

features used by 364

Google 10–11, 345, 349, 351–352, 363–364, 405, 489

keyword-based advertising and 385–386

keyword pricing mechanisms 229–230

link assessment 353

markets for keywords 389

and navigational/transactional links 340

optimization of 365

organic search results 386, 405–406

page ranking in 351–352, 365

tools/recommendation systems 489

Yahoo! 363

*See also *authorities, hubs, meta-search, PageRank, Web searches

second-price sealed-bid auctions 226, 229–232, 277

trading networks and 290–291

truthful bidding at 230–232

vs. ascending bid auctions 228–229

winning bid at 230

*See also *Vickrey-Clarke-Groves (VCG) mechanism

segregation 96–103

*See also *Schelling segregation model

selection

friendships and 81–82

homophily and 83

and social influence 82–83, 94–96

*See also *socialization

self-fulfilling expectations equilibrium 454–456, 625

self-negating expectations 472

sellers 9, 37, 249, 255, 261, 277–300

semantic networks 338–339

Seoul, Korea 210

sequential voting 672–673

sexual contact network 582

sexually transmitted diseases (STDs) 29, 567

shared resources 8, 320, 685

Shiite religious institutions 517

short paths 31–32, 34, 303, 333, 338, 537–543, 549, 551–552

shortest paths 29, 39, 67–68, 71–74, 542, 556

signaling quality 631–632

simple paths 25

sincere voting 664, 667

single-parent ancestry 587–588, 590

single-peaked preferences 658–663

SIR epidemic model 572–576, 577–578

SIRS epidemic model 580–581

SIS epidemic model 576–578

six degrees of separation 7, 30–32, 338, 537–538, 552

SixDegrees.com 6

Slashdot 113

small-world contact networks 580–582

small-world phenomenon 7, 30–32, 537–565

hypertext and 336

Web 2.0 and 349

social-affiliation networks 86, 92

social capital 61–62

social contagion 14–15, 83, 568–569

social distance 549–551

social exchange 249, 302

social foci 84*f*, 86*f*, 88, 103, 126, 549–551

social gatekeeping 40, 60

social influence 81–82

and diffusion of innovations 497–498

selection and 82–83, 94–96

social institutions 516–517, 607–608

social movements 511

social networks 1

coevolution of affiliation and 86–88

communication/interaction-based 3*f*

described 23

and homophily 77–83

local bridges in 46–51, 510–511

power in 301–303

strength of weak ties principle 7, 43

tie strength in 48

tracking link formation in online data 88–96

and triadic closure 44

Web-based 6, 12, 12*f*

*See also *Facebook, Twitter

social optimality 166–167

social relationships 302

social sanctions 59

social status 312, 552–554

social welfare 212, 257, 275–276

in markets 453

in trading networks 294

socialization 82

socially optimal traffic pattern 211–212

Sotheby's auction house 225

spam filtering (and Bayes' rule) 433–434

spectral analysis 368, 374–376

stability 315, 456–459

stable equilibria 462

stable outcomes 314–317

core solution's relation to 320

lack of, on triangle network 316–317

Ultimatum Game's relation to 317

Stag Hunt game 153–154, 172, 197–198

standard deviation (of a normal distribution) 480

state prices 616–621

states (cascade model) 437–438

states of the world (cascade model) 437

stationary equilibrium 325–326

stationary strategies 325–326

stem graph 307–310, 319–320

stock market 278, 280, 297

ask (in stock transaction) 279

asymmetric information in 630–631

bid (in stock transaction) 279

strategies (in games) 142

strength of weak ties hypothesis 43

strict Nash equilibrium 198

strictly dominant strategy (in games) 143, 147–149, 171–172

strictly dominated strategy (in games) 168–173

Strogatz, Steve 539–541

*See under *Watts-Strogartz model

strong ties 7, 48–50, 52, 54, 57–58, 74, 511, 515–516

Strong Triadic Closure property 47–50, 74

strongly connected components (SCC) in directed graphs 342–344

structural balance 8, 107–110, 133

applications of 113–115

approximate 113, 127–132

in arbitrary (noncomplete) networks 119–127

characterizations of 110–112

definition 109–110, 118–119

triangle formations and 115–116

weak form of 115–118

*See also *Characterization of Weakly Balanced Networks, Weak Structural Balance Property

Structural Balance Property 109–110, 135

structural effects 13–15

structural holes (graph theory) 7, 60–62, 67, 303, 511

subgame perfect Nash equilibrium 286, 322

suicide 45–46

Sunni religious institutions 517

Super Bowl commercials 517

supernodes 123–126, 343

supply (of goods) 452, 455

Surowiecki, James 443, 617

surplus 227, 301, 311, 320, 324

surrounding contexts (of a network) 77

symmetric game 196–198, 200, 205

symmetric information 624

symmetric matrix 371–372, 375–376

synchronization (of epidemics) 578–582

synonymy 351

syphilis epidemic 579, 582

technological networks 38

three-node path (in network exchange theory) 306, 312, 314, 316, 327, 329

thresholds

heterogeneous 512–514

for participation in collective action 514–517

in Schelling segregation model 97–98

social movements and 511

tie strength 50

edge sorting by 52

on Facebook 54–57

and local bridges 49–51

and neighborhood overlap 52–54

social network connections 51

on Twitter 57–58

ties

*See *strong ties, weak ties

tightly-knit regions 62–67, 69–70

time-expanded contact network 578, 579*f*

tipping point 457, 463–465, 467

trade on networks 280–286, 297

trader profits 295–297, 299

trading networks

for agricultural markets 281*f*

conventions (representations) 282

equilibria in 286–290, 296, 297

ripple effects/shocks to 291

and second-price sealed-bid auctions 290–291

social welfare in 294

traffic

congestion pattern 8, 207–208, 470

edges of high betweenness and 68

node to node movement 25

traffic as a game

dominant strategy in 209–210

Nash equilibrium in 208–209

payoffs for players 208, 212

progress measure analysis 213–215

social welfare maximizers in 212

traffic at equilibrium 207–209

pattern searches 212–217

social cost of 211–212

vs. the social optimum 217–219

traffic pattern

potential energy of 213–215

social cost of 211

socially optimal 211–212

“The Tragedy of the Commons” article (Hardin) 685–688

transactional links (World Wide Web) 340

transient contacts 582–584

transportation networks 24*f*, 207–208

transpose (of a matrix) 370

travel patterns (and epidemics) 567

travel-time function 211

Treasury bills 225

tree network 574–575, 591–594, 597, 602

triadic closure 44–46, 74

clustering coefficient 44–45

empirical studies of 89–91

homophily and 79, 89

reasons for 45–46

and social-affiliation networks 87*f*

strong/weak ties and 49

structure/randomness and 539–540

Web 2.0 and 349

*See also *Strong Triadic Closure property

triangle network 308

lack of stable outcomes in 316–317

triangles 44, 47, 60, 66–67

balanced 109

counting 129

and structural balance 115–116

unbalanced 109–110, 129–130, 132, 133–135

trust 45, 49, 59, 62, 114–115, 349

trust-distrust dichotomy 114–115

trust systems 349

truthful bidding (second-price auctions) 230–232

tuberculosis outbreak 14–15

Twitter (microblogging service) 348, 352

tie strength on 57–58

two-node path (in network exchange theory) 306, 310

Ultimatum Game 310, 316

payoffs in 314

power imbalances in 312–314

results of experiments on 313–314

stable outcomes and 316

Unanimity 657–658, 668, 671–672, 673–675

unanimity rule 668–672

unbalanced coordination game 152

unbalanced triangle formations 109–110, 129–130, 132, 133–135

undirected graph 21, 22*f*

United States Patent and Trademark Office 691

unstable equilibria 462

unstable networks 308–309

upgrading of networks 210

U.S. Postal Service 546

used-car markets 622–624, 628, 630–632, 634, 642–643

user talk pages (in Wikipedia) 92

utility function 611–615, 617, 624

valuations 253–254, 255

value in social relationships 302

Vanguard 279

vestigial behavior 525, 529

VHS technology 464

Vickrey, William 226

Vickrey-Clarke-Groves (VCG) mechanism 387, 401

dominance of truth-telling in 395–398

and pollution control 684

prices and the market-clearing property 407–409

Vickrey-Clarke-Groves (VCG) principle 391–395

application to matching markets 392–394

described 392

posted prices/personalized prices 395

price-setting procedure 394–395

viral ideas 6

viral marketing 504–505

virus game 195, 203

voting

f-majority rule 672

for group decision making 645–646

by in-links 353

individual preferences 646–648

and information aggregation 663–668

insincere voting 665–668

majority rule system 649–653, 655–658, 661, 662–663, 665, 667

Median Voter Theorem 658–663

misreporting of preferences 655–657

plurality voting 656

polarizing alternative and 674–675, 677

positional voting 654–656

profile 673–677

sequential voting 672–673

sincere voting 664, 667

single-peaked preferences 658–663

*See also *Arrow's Impossibility Theorem, Unanimity, unanimity rule

voting systems 16–17, 645–647

and Arrow's Impossibility Theorem 673–676

based on majority rule 651–653

dictatorships 658, 674–675

IIA/Unanimity and 657–658

and positional voting 654–656

Watts, Duncan 539–541

Watts-Strogatz model 539–541, 580–581

waves (of a branching process) 569

weak power 307, 308, 310, 317, 320

Weak Structural Balance Property 116–117

weak ties 7

on Facebook 57–58

generalizing notions of 52

local bridges and 49–51

strength of 43, 46–51, 510

and Watts-Strogatz model 539–541

weakly balanced networks 116–118

weakly dominated strategies (in games) 172–173

wealth dynamics 635–641

wealth shares 617–619, 635, 639–640

Web 2.0 347–349

Web browsers 334, 341

Web pages 334, 481–483, 486, 489–490

Web searches

abundance/scarcity problems 352

algorithmic results 386

clickthrough data 364

clickthrough rates/revenues per click 386

dynamic aspects of 352–353

hubs and authorities 356–358, 364

information retrieval 351–353, 365

link analysis applied in 363–365

list-finding heuristic 353–354

markets for keywords 389

“News Search,” 352

organic search results 386, 405–406

principle of repeated improvement 355–356

ranking problems 351–352

voting by in-links 353

*See also *PageRank, search engines

who-talks-to-whom (networks) 37, 51–52, 90, 551

Wikipedia 11*f*, 36, 37–38, 92–95, 337–338, 345, 348, 479

willingness to pay (by consumers) 451, 454

Windows 505

winner's curse (in auctions) 233–234

wisdom of crowds 348–349, 615–618, 641–642

*The Wisdom of Crowds* (Surowiecki) 443, 617

word association studies 338–339

word frequency 489

World of Warcraft (WoW) 36

World War I 113, 114*f*

World Wide Web 23, 37–38, 58, 333–335

bow-tie structure of 344–347, 350

citation networks vs. 336*f*

as a directed graph 340–344

evolution of 339–340

in-links 353–354, 357, 359, 366, 382, 479–480, 482, 490, 493

modeling link creation in 483–484

navigational/transactional links 340

popularity and 479, 484–486, 489

*See also *search engines, Web searches

Wright-Fisher model (of single-parent ancestry) 587–588, 590

Yahoo! (company) 225, 385

Yahoo! Answers 91

YouTube 5*f*, 13, 348

Zachary, Wayne 2, 64, 70

zeroed-out market 412, 414, 419–420

zeroing out a buyer 411–413, 418

Zipf, George Kingsley 488–489

Zipf plots 488

Zipf's Law 489

© Cambridge University Press