216 Handbook of Big Data
graphs. In Proceedings of the 23rd International Conference on World Wide Web,
pp. 349–360. ACM, New York, 2014.
11. Johan Ugander and Lars Backstrom. Balanced label propagation for partitioning
massive graphs. In Proceedings of the 6th ACM International Conference on Web Search
and Data Mining, pp. 507–516. ACM, New York, 2013.
12. Leman Akoglu, Mary McGlohon, and Christos Faloutsos. Oddball: Spotting anomalies
in weighted graphs. In Mohammed Zaki, Jeffrey Yu, B. Ravindran, and Vikram Pudi
(eds.), Advances in Knowledge Discovery and Data Mining, volume 6119 of Lecture
Notes in Computer Science, pp. 410–421. Springer, Berlin, Germany, 2010.
13. Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and
algorithms. ACM Computing Surveys, 38(1):2, 2006.
14. Stefan Bornholdt and Heinz G. Schuster (eds.). Handbook of Graphs and Networks:
From the Genome to the Internet. John Wiley & Sons, Weinheim, Germany, 2003.
15. Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized PageRank
on MapReduce. In Proceedings of the International Conference on Management of Data,
pp. 973–984. ACM, New York, 2011.
16. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank
citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford
University, November 1999.
17. Jia-Yu Pan, Hyung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu. Automatic
multimedia cross-modal correlation discovery. In Proceedings of the 10th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, pp. 653–658. ACM,
New York, 2004.
18. Jeremy V. Kepner and John Gilbert. Graph Algorithms in the Language of Linear
Algebra. SIAM, Philadelphia, PA, 2011.
19. Dirk Kosch¨utzki, Katharina A. Lehmann, Leon Peeters, Stefan Richter, Dagmar
Tenfelde-Podehl, and Oliver Zlotowski. Centrality indicies. In Ulrik Brandes and
Thomas Erlebach (eds.), Network Analysis: Methodological Foundations, volume 3418
of Lecture Notes in Computer Science, Chapter 3, pp. 16–61. Springer, Berlin, Germany,
2005.
20. David F. Gleich. PageRank beyond the web. SIAM Review, 57(3):321–363, August 2015.
21. Grzegorz Malewicz, Matthew H. Austern, Aart J.C. Bik, James C. Dehnert, Ilan Horn,
Naty Leiser, and Grzegorz Czajkowski. Pregel: A system for large-scale graph process-
ing. In Proceedings of the ACM SIGMOD International Conference on Management of
Data, pp. 135–146. ACM, New York, 2010.
22. Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin.
Powergraph: Distributed graph-parallel computation on natural graphs. In Presented
as Part of the 10th USENIX Symposium on Operating Systems Design and Implemen-
tation, pp. 17–30. USENIX, Hollywood, CA, 2012.
23. Julian Shun and Guy E. Blelloch. Ligra: A lightweight graph processing framework for
shared memory. SIGPLAN Notices, 48(8):135–146, February 2013.
24. Christopher R. Palmer, Phillip B. Gibbons, and Christos Faloutsos. ANF: A fast and
scalable tool for data mining in massive graphs. In Proceedings of the 8th ACM SIGKDD
Mining Large Graphs 217
International Conference on Knowledge Discovery and Data Mining, pp. 81–90. ACM,
New York, 2002.
25. Paolo Boldi, Marco Rosa, and Sebastiano Vigna. HyperANF: Approximating the
neighbourhood function of very large graphs on a budget. In Proceedings of the 20th
International Conference on World Wide Web, pp. 625–634. ACM, New York, 2011.
26. Milena Mihail. Conductance and convergence of Markov chains-a combinatorial treat-
ment of expanders. In 30th Annual Symposium on Foundations of Computer Science,
pp. 526–531. IEEE, Research Triangle Park, NC, October 30–November 1, 1989.
27. Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal,
23(98):298–305, 1973.
28. Richard B. Lehoucq, Danny C. Sorensen, and Chao Yang. ARPACK User’s Guide:
Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods.
SIAM Publications, Philadelphia, PA, October 1997.
29. Risi I. Kondor and John D. Lafferty. Diffusion kernels on graphs and other discrete
input spaces. In Proceedings of the 19th International Conference on Machine Learning,
pp. 315–322. Morgan Kaufmann Publishers, San Francisco, CA, 2002.
30. Aaron B. Adcock, Blair D. Sullivan, Oscar R. Hernandez, and Michael W. Mahoney.
Evaluating OpenMP tasking at scale for the computation of graph hyperbolicity. In
Proceedings of the 9th IWOMP, pp. 71–83. Springer, Berlin, Germany, 2013.
31. Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using PageRank
vectors. In Proceedings of the 47th Annual IEEE Symposium on Foundations of
Computer Science, pp. 475–486. IEEE, Berkeley, CA, 2006.
32. David F. Gleich and Michael M. Mahoney. Anti-differentiating approximation
algorithms: A case study with min-cuts, spectral, and flow. In Proceedings of the
International Conference on Machine Learning, pp. 1018–1025, 2014.
33. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. Commu-
nity structure in large networks: Natural cluster sizes and the absence of large well-
defined clusters. Internet Mathematics, 6(1):29–123, 2009.
34. Jonathan Cohen. Graph twiddling in a MapReduce world. Computing in Science and
Engineering, 11(4):29–41, 2009.
35. U Kang, Duen H. Chau, and Christos Faloutsos. PEGASUS: A peta-scale graph mining
system implementation and observations. In 9th IEEE International Conference on
Data Mining, pp. 229–238, IEEE, Miami, FL, December 2009.
36. Jimmy Lin and Chris Dyer. Data-Intensive Text Processing with MapReduce. Morgan &
Claypool, San Rafael, CA, 2010.
37. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner (eds.),
Graph Partitioning and Graph Clustering. 10th DIMACS Implementation Challenge
Workshop, volume 588 of Contemporary Mathematics. American Mathematical Society,
Providence, RI, 2013.
38. Michael W. Mahoney, Lorenzo Orecchia, and Nisheeth K. Vishnoi. A local spectral
method for graphs: With applications to improving graph partitions and exploring data
graphs locally. Journal of Machine Learning Research, 13:2339–2365, August 2012.
218 Handbook of Big Data
39. U. Kang and Christos Faloutsos. Beyond ‘caveman communities’: Hubs and spokes
for graph compression and mining. In Proceedings of the IEEE 11th International
Conference on Data Mining, pp. 300–309. IEEE, Washington, DC, 2011.
40. Ronald Burt. Structural Holes: The Social Structure of Competition.HarvardUniversity
Press, Cambridge, MA, 1995.
41. Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last
reducer. In Proceedings of the 20th International Conference on World Wide Web,
pp. 607–614. ACM, New York, 2011.
42. Leo Katz. A new status index derived from sociometric analysis. Psychometrika,
18(1):39–43, March 1953.
43. Fan Chung. The heat kernel as the PageRank of a graph. Proceedings of the National
Academy of Sciences USA, 104(50):19735–19740, December 2007.
44. Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive
graphs and its application to nearly-linear time graph partitioning. arXiv: cs.DS:
0809.3232, 2008.
45. Frank Lin and William Cohen. Power iteration clustering. In Proceedings of the 27th
International Conference on Machine Learning, 2010.
46. Andreas M. Lisewski and Olivier Lichtarge. Untangling complex networks: Risk
minimization in financial markets through accessible spin glass ground states. Physica
A: Statistical Mechanics and its Applications, 389(16):3250–3253, 2010.
47. Danai Koutra, Tai-You Ke, U. Kang, Duen Horng Chau, Hsing-Kuo Kenneth Pao,
and Christos Faloutsos. Unifying guilt-by-association approaches: Theorems and fast
algorithms. In ECML/PKDD, pp. 245–260, Springer, Berlin, Germany, 2011.
48. Mark E. J. Newman. Finding community structure in networks using the eigenvectors
of matrices. Physical Review E, 74(3):036104, September 2006.
49. Francesco Bonchi, Pooya Esfandiar, David F. Gleich, Chen Greif, and Laks V.S.
Lakshmanan. Fast matrix computations for pairwise and columnwise commute times
and Katz scores. Internet Mathematics, 8(1–2):73–112, 2012.
50. Rumi Ghosh, Shang-hua Teng, Kristina Lerman, and Xiaoran Yan. The interplay
between dynamics and networks: Centrality, communities, and Cheeger inequality.
In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, pp. 1406–1415. ACM, New York, 2014.
51. Sebastiano Vigna. Spectral ranking. arXiv: cs.IR:0912.0238, 2009.
52. Ricardo Baeza-Yates, Paolo Boldi, and Carlos Castillo. Generalizing PageRank: Damp-
ing functions for link-based ranking algorithms. In Proceedings of the 29th Annual
International ACM SIGIR Conference on Research and Development in Information
Retrieval, pp. 308–315. ACM, Seattle, WA, August 2006.
53. Julie L. Morrison, Rainer Breitling, Desmond J. Higham, and David R. Gilbert.
GeneRank: Using search engine technology for the analysis of microarray experiments.
BMC Bioinformatics, 6(1):233, 2005.
54. Dengyong Zhou, Olivier Bousquet, Thomas N. Lal, Jason Weston, and Bernhard
Sch¨olkopf. Learning with local and global consistency. In NIPS, pp. 321–328, 2003.
Mining Large Graphs 219
55. Satu E. Schaeffer. Graph clustering. Computer Science Review, 1(1):27–64, 2007.
56. Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski. Overlapping community
detection in networks: The state-of-the-art and comparative study. ACM Computing
Surveys, 45(4):43:1–43:35, August 2013.
57. Lucas G. S. Jeub, Prakash Balachandran, Mason A. Porter, Peter J. Mucha, and
Michael W. Mahoney. Think locally, act locally: Detection of small, medium-sized, and
large communities in large networks. Physical Review E, 91:012821, January 2015.
58. Joyce J. Whang, David F. Gleich, and Inderjit S. Dhillon. Overlapping community
detection using seed set expansion. In Proceedings of the 22nd ACM International
Conference on Conference on Information and Knowledge Management, pp. 2099–2108.
ACM, New York, October 2013.
59. Kyle Kloster and David F. Gleich. Heat kernel based community detection. In Proceed-
ings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and
Data Mining, pp. 1386–1395. ACM, New York, 2014.
60. Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure
for graph analytics. In Proceedings of the 24th ACM Symposium on Operating Systems
Principles, pp. 456–471. ACM, New York, 2013.
61. K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova. Monte carlo methods in
PageRank computation: When one iteration is sufficient. SIAM Journal on Numerical
Analysis, 45(2):890–904, February 2007.
62. Christian Borgs, Michael Brautbar, Jennifer Chayes, and Shang-Hua Teng. Multi-scale
matrix sampling and sublinear-time PageRank computation. Internet Mathemat-
ics, Available online http://dx.doi.org/10.1080/15427951.2013.802752. Accessed on
October 23, 2015. 2013.
63. Stephen R. Troyer. Sparse matrix multiplication. Technical Report ILLIAC IV Docu-
ment Number 191, University of Illinois, Urbana-Champagne, 1968.
64. B. A. Carr´e. An algebra for network routing problems. IMA Journal of Applied
Mathematics, 7(3):273–294, 1971.
65. M. Bayati, D. Shah, and M. Sharma. Max-product for maximum weight matching:
Convergence, correctness, and LP duality. IEEE Transactions on Information Theory,
54(3):1241–1251, March 2008.
66. Pan Zhang and Cristopher Moore. Scalable detection of statistically significant commu-
nities and hierarchies, using message passing for modularity. Proceedings of the National
Academy of Sciences USA, 111(51):18144–18149, 2014.
67. Aydn Bulu¸c and John R. Gilbert. The Combinatorial BLAS: Design, implementation,
and applications. International Journal of High Performance Computing Applications,
25(4):496–509, November 2011.
68. K. J. Maschhoff and D. C. Sorensen. P
ARPACK: An efficient portable large scale
eigenvalue package for distributed memory parallel architectures. In Proceedings of the
3rd International Workshop on Applied Parallel Computing, Industrial Computation
and Optimization, volume 1184 of LNCS, pp. 478–486. Springer, London, 1996.
220 Handbook of Big Data
69. C.E. Tsourakakis. Fast counting of triangles in large real networks without counting:
Algorithms and laws. In Proceedings of the 8th IEEE International Conference on Data
Mining, pp. 608–617. ICDM, Pisa, Italy, December 2008.
70. Usha N. Raghavan, R´eka Albert, and Soundar Kumara. Near linear time algorithm
to detect community structures in large-scale networks. Physical Review E, 76:036106,
September 2007.
71. Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. Layered label
propagation: A multiresolution coordinate-free ordering for compressing social networks.
In Proceedings of the 20th WWW2011, pp. 587–596, ACM, New York, March 2011.
72. Philippe Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base
applications. Journal of Computer and System Sciences, 31(2):182–209, September
1985.
73. Philippe Flajolet,
´
Eric Fusy, Olivier Gandouet, and Fr´ed´eric Meunier. HyperLogLog:
The analysis of a near-optimal cardinality estimation algorithm. In Conference on
Analysis of Algorithms, pp. 127–146, DMTCS, Nancy, France, 2007.
74. Jeffrey Cohen, Brian Dolan, Mark Dunlap, Joseph M. Hellerstein, and Caleb Welton.
MAD skills: New analysis practices for Big Data. Proceedings of the VLDB Endowment,
2(2):1481–1492, August 2009.
75. A. T. Adai, S. V. Date, S. Wieland, and E. M. Marcotte. LGL: Creating a map of protein
function with an algorithm for visualizing very large biological networks. Journal of
Molecular Biology, 340(1):179–190, June 2004.
76. Shawn Martin, W. Michael Brown, Richard Klavans, and Kevin W. Boyack. OpenOrd:
an open-source toolbox for large graph layout. Proceedings of SPIE, 7868:786806–
786806-11, 2011.
77. Gunnar Klau. A new graph-based method for pairwise global network alignment. BMC
Bioinformatics, 10(Suppl 1):S59, January 2009.
78. Martin Krzywinski, Inanc Birol, Steven J.M. Jones, and Marco A. Marra. Hive plots–
rational approach to visualizing networks. Briefings in Bioinformatics, 13(5):627–644,
2012.
79. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in
networks. Physical Review E, 69(2):026113, Februery 2004.
80. Madhav Jha, Comandur Seshadhri, and Ali Pinar. A space efficient streaming algo-
rithm for triangle counting using the birthday paradox. In Proceedings of the 19th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
pp. 589–597. ACM, New York, 2013.
81. Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Record, 43(1):9–20,
May 2014.
82. Xin Sui, Tsung-Hsien Lee, Joyce J. Whang, Berkant Savas, Saral Jain, Keshav Pingali,
and Inderjit Dhillon. Parallel clustered low-rank approximation of graphs and its
application to link prediction. In Hironori Kasahara and Keiji Kimura (eds.), Languages
and Compilers for Parallel Computing, volume 7760 of Lecture Notes in Computer
Science, pp. 76–95. Springer, Berlin, Germany, 2013.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.