Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 167-190).

Acknowledgments -- 1. Introduction --

Part I. Patterns and laws -- 2. Patterns in static graphs -- 2.1 S-1: heavy-tailed degree distribution -- 2.2 S-2: Eigenvalue power law (EPL) -- 2.3 S-3 small diameter -- 2.4 S-4, S-5: triangle power laws (TPL, DTPL) --

3. Patterns in evolving graphs -- 3.1 D-1: shrinking diameters -- 3.2 D-2: densification power law (DPL) -- 3.3 D-3: diameter-plot and gelling point -- 3.4 D-4: oscillating NLCCs sizes -- 3.5 D-5: LPL, principal Eigenvalue over time --

4. Patterns in weighted graphs -- 4.1 W-1: snapshot power laws (SPL) "fortification" -- 4.2 DW-1: weight power law (WPL) -- 4.3 DW-2: LWPL, weighted principal Eigenvalue over time --

5. Discussion, the structure of specific graphs -- 5.1 The internet -- 5.2 The World Wide Web (WWW) --

6. Discussion, power laws and deviations -- 6.1 Power Laws, slope estimation -- 6.2 Deviations from power laws -- 6.2.1 Exponential cutoffs -- 6.2.2 Lognormals or the "DGX" distribution -- 6.2.3 Doubly-Pareto lognormal (dPln) --

7. Summary of patterns --

Part II. Graph generators -- 8. Graph generators -- 8.1 Random graph models -- 8.1.1 The Erdös-Rényi random graph model -- 8.1.2 Generalized random graph models --

9. Preferential attachment and variants -- 9.1 Main ideas -- 9.1.1 Basic preferential attachment -- 9.1.2 Initial attractiveness -- 9.1.3 Internal edges and rewiring -- 9.2 Related methods -- 9.2.1 Edge copying models -- 9.2.2 Modifying the preferential attachment equation -- 9.2.3 Modeling increasing average degree -- 9.2.4 Node fitness measures -- 9.2.5 Generalizing preferential attachment -- 9.2.6 Pagerank-based preferential attachment -- 9.2.7 The forest fire model -- 9.3 Summary of preferential attachment models --

10. Incorporating geographical information -- 10.1 Early models -- 10.1.1 The small-world model -- 10.1.2 The Waxman model -- 10.1.3 The BRITE generator -- 10.1.4 Other geographical constraints -- 10.2 Topology from resource optimizations -- 10.2.1 The highly optimized tolerance model -- 10.2.2 The heuristically optimized tradeoffs model -- 10.3 Generators for the internet topology -- 10.3.1 Structural generators -- 10.3.2 The Inet topology generator -- 10.4 Comparison studies --

11. The RMAT (recursive MATrix) graph generator --

12. Graph generation by Kronecker multiplication --

13. Summary and practitioner's guide --

Part III. Tools and case studies -- 14. SVD, random walks, and tensors -- 14.1 Eigenvalues, definition and intuition -- 14.2 Singular value decomposition (SVD) -- 14.3 HITS: hubs and authorities -- 14.4 PageRank --

15. Tensors -- 15.1 Introduction -- 15.2 Main ideas -- 15.3 An example: tensors at work -- 15.4 Conclusions, practitioner's guide --

16. Community detection -- 16.1 Clustering coefficient -- 16.2 Methods for extracting graph communities -- 16.3 A word of caution "no good cuts" --

17. Influence/virus propagation and immunization -- 17.1 Introduction, terminology -- 17.2 Main result and its generality -- 17.3 Applications -- 17.4 Discussion -- 17.4.1 Simulation examples -- 17.4.2 Measure of connectivity -- 17.5 Conclusion --

18. Case studies -- 18.1 Proximity and random walks -- 18.2 Automatic captioning, multi-modal querying -- 18.2.1 The GCap method -- 18.2.2 Performance and variations -- 18.2.3 Discussion -- 18.2.4 Conclusions -- 18.3 Center-piece subgraphs, who is the mastermind? --

Part IV. Outreach, related work -- 19. Social networks -- 19.1 Mapping social networks -- 19.2 Dataset characteristics -- 19.3 Structure from data -- 19.4 Social "roles" -- 19.5 Social capital -- 19.6 Recent research directions -- 19.7 Differences from graph mining --

20. Other related work -- 20.1 Relational learning -- 20.2 Finding frequent subgraphs -- 20.3 Navigation in graphs -- 20.3.1 Methods of navigation -- 20.3.2 Relationship between graph topology and ease of navigation -- 20.4 Using social networks in other fields --

21. Conclusions -- 21.1 Future research directions -- 21.2 Parting thoughts --

Resources -- Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

What does the Web look like? How can we find patterns, communities, outliers, in a social network? Which are the most central nodes in a network? These are the questions that motivate this work. Networks and graphs appear in many diverse settings, for example in social networks, computer-communication networks (intrusion detection, traffic management), protein-protein interaction networks in biology, document-text bipartite graphs in text retrieval, person-account graphs in financial fraud detection, and others. In this work, first we list several surprising patterns that real graphs tend to follow. Then we give a detailed list of generators that try to mirror these patterns. Generators are important, because they can help with "what if " scenarios, extrapolations, and anonymization. Then we provide a list of powerful tools for graph analysis, and specifically spectral methods (Singular Value Decomposition (SVD)), tensors, and case studies like the famous "pageRank" algorithm and the "HITS" algorithm for ranking web search results. Finally, we conclude with a survey of tools and observations from related fields like sociology, which provide complementary viewpoints.

Also available in print.

Title from PDF t.p. (viewed on November 20, 2012).