H. Garcia-molina, 14) Christos Faloutsos (0.13) Victor Vianu (0.13)

E. A. Fox, 09) Beng Chin Ooi (0.08

A. Volovich and H. , Partouche Barak Kol Shmuel Elitzur Shmuel Elitzur A

L. Akoglu, P. O. Vaz-de-melo, and C. Faloutsos, Quantifying Reciprocity in Large Weighted Communication Networks, In PAKDD, issue.2, p.2012
DOI : 10.1007/978-3-642-30220-6_8

J. , I. Alvarez-hamelin, L. Dall-'asta, A. Barrat, and A. Vespignani, Large scale networks fingerprinting and visualization using the k-core decomposition, Advances in Neural Information Processing Systems 18, pp.41-50, 2006.

J. Ignacio-alvarez-hamelin, L. Dall-'asta, A. Barrat, and A. Vespignani, k-core decomposition: a tool for the visualization of large scale networks, 2005.

Y. An, J. Janssen, and E. E. Milios, Characterizing and Mining the Citation Graph of the Computer Science Literature, Knowledge and Information Systems, vol.393, issue.6, pp.664-678, 2004.
DOI : 10.1007/s10115-003-0128-3

R. Andersen and K. Chellapilla, Finding Dense Subgraphs with Size Bounds, WAW, pp.25-37, 2009.
DOI : 10.1007/978-3-540-95995-3_3

T. Antal, S. Krapivsky, and . Redner, Dynamics of social balance on networks, Physical Review E, vol.72, issue.3, p.72, 2005.
DOI : 10.1103/PhysRevE.72.036121

D. Arthur and S. Vassilvitskii, k-means++: the advantages of careful seeding, SODA, pp.1027-1035, 2007.

D. Gary, C. W. Bader, and . Hogue, An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics, pp.1-1, 2003.

A. Barabási and R. Albert, Emergence of scaling in random networks, Science, vol.286, pp.509-512, 1999.

A. Barabasi, R. Albert, and H. Jeong, Scale-free characteristics of random networks: the topology of the world-wide web, Physica A: Statistical Mechanics and its Applications, vol.281, issue.1-4, 2000.
DOI : 10.1016/S0378-4371(00)00018-2

V. Batagelj and A. Mrvar, Pajek -analysis and visualization of large networks, Graph Drawing, pp.8-11, 2002.

V. Batagelj and M. Zaversnik, Generalized cores, 2002.

V. Batagelj and M. Zaversnik, An o(m) algorithm for cores decomposition of networks. CoRR, cs, 2003.

M. Baur, M. Gaertler, R. Görke, M. Krug, and D. Wagner, Generating Graphs with Predefined k-Core Structure, Proceedings of the European Conference of Complex Systems (ECCS'07), 2007.

B. Bollobás, The evolution of sparse graphs, Graph theory and combinatorics, pp.35-57, 1983.

B. Bollobas, C. Borgs, J. Chayes, and O. Riordan, Directed scale-free graph, Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp.132-139, 2003.

B. Bollobás and O. Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, vol.24, issue.1, pp.5-34, 2004.
DOI : 10.1007/s00493-004-0002-2

U. Brandes, P. Kenis, J. Lerner, and D. Van-raaij, Network analysis of collaboration structure in Wikipedia, Proceedings of the 18th international conference on World wide web, WWW '09, 2009.
DOI : 10.1145/1526709.1526808

G. Pierce, D. Buckley, and . Osthus, Popularity based random graph models leading to a scale-free degree sequence, Discrete Mathematics, vol.282, pp.53-68, 2001.

S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, and E. Shir, Medusa -new model of internet topology using k-shell decomposition, 2006.

M. Charikar, Greedy Approximation Algorithms for Finding Dense Components in a Graph, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX '00, pp.84-95, 2000.
DOI : 10.1007/3-540-44436-X_10

W. Chen, Y. Song, H. Bai, C. Lin, and E. Y. Chang, Parallel Spectral Clustering in Distributed Systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.3, pp.568-586, 2011.
DOI : 10.1109/TPAMI.2010.88

X. Chen and D. Cai, Large scale spectral clustering with landmarkbased representation, AAAI, 2011.

A. Clauset, M. E. Newman, and C. Moore, Finding community structure in very large networks, Physical Review E, vol.70, issue.6, p.66111, 2004.
DOI : 10.1103/PhysRevE.70.066111

C. Cooper and A. Frieze, A general model of web graphs. Random Struct, Algorithms, vol.22, pp.311-335, 2003.

C. Dangalchev, Residual closeness in networks Physica A: Statistical Mechanics and its Applications, pp.556-564, 2006.

C. De, K. , and P. Van-dooren, The pagetrust algorithm: How to rank web pages when negative links are allowed, SDM, 2008.

R. Diestel, Graph theory, Graduate Texts in Mathematics, vol.173, 2005.

S. N. Dorogovtsev, J. F. Mendes, and A. N. Samukhin, Structure of Growing Networks with Preferential Linking, Physical Review Letters, vol.85, issue.21, pp.4633-4636, 2000.
DOI : 10.1103/PhysRevLett.85.4633

S. N. Dorogovtsev, A. V. Goltsev, and J. F. Mendes, -Core Organization of Complex Networks, Physical Review Letters, vol.96, issue.4, p.40601, 2006.
DOI : 10.1103/PhysRevLett.96.040601

P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, vol.56, issue.1-3, 2004.
DOI : 10.1023/B:MACH.0000033113.59016.96

L. Egghe, Theory and practise of the g-index, Scientometrics, vol.69, issue.1, pp.131-152, 2006.
DOI : 10.1007/s11192-006-0144-7

P. Erd?-os and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl, vol.5, pp.17-61, 1960.

P. Erd? and O. , On the structure of linear graphs, Israel J. Math, vol.1, pp.156-160, 1963.

M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, vol.29, issue.4, pp.251-262, 1999.
DOI : 10.1145/316194.316229

S. Fortunato, Community detection in graphs, Physics Reports, vol.486, issue.3-5, pp.75-174, 2010.
DOI : 10.1016/j.physrep.2009.11.002

E. C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM, vol.29, issue.1, pp.24-32, 1982.
DOI : 10.1145/322290.322292

D. Garlaschelli and M. I. Loffredo, Patterns of Link Reciprocity in Directed Networks, Physical Review Letters, vol.93, issue.26, p.93, 2004.
DOI : 10.1103/PhysRevLett.93.268701

M. Girvan and M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, vol.99, issue.12, pp.7821-7826, 2002.
DOI : 10.1073/pnas.122653799

F. David, C. Gleich, and . Seshadhri, Vertex neighborhoods, low conductance cuts, and good seeds for local community methods, KDD, 2012.

R. Guha, R. Kumar, P. Raghavan, and A. Tomkins, Propagation of trust and distrust, Proceedings of the 13th conference on World Wide Web , WWW '04, 2004.
DOI : 10.1145/988672.988727

J. Healy, J. Janssen, E. Milios, and W. Aiello, Characterization of graphs using degree cores In Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, volume LNCS-4936 of Lecture Notes in Computer Science, 2008.

J. E. Hirsch, An index to quantify an individual's scientific research output, Proceedings of the National Academy of Sciences, vol.102, issue.46, pp.16569-16572, 2005.
DOI : 10.1073/pnas.0507655102

S. Janson and M. J. Luczak, Asymptotic normality of the k -core in random graphs, The Annals of Applied Probability, vol.18, issue.3, pp.1085-11370378, 2008.
DOI : 10.1214/07-AAP478

V. Kandylas, S. Upham, and L. Ungar, Finding cohesive clusters for analyzing knowledge communities, Knowledge and Information Systems, vol.7, issue.2, pp.335-354, 2008.
DOI : 10.1007/s10115-008-0135-5

G. Karypis and V. Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, vol.20, issue.1, pp.359-392, 1998.
DOI : 10.1137/S1064827595287997

M. Lefteris, D. M. Kirousis, and . Thilikos, The linkage of a graph, SIAM J. Comput, vol.25, issue.3, pp.626-647, 1996.

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins et al., Stochastic models for the Web graph, Proceedings 41st Annual Symposium on Foundations of Computer Science, p.57, 2000.
DOI : 10.1109/SFCS.2000.892065

R. Kumar, P. Raghavan, A. Sridhar-rajagopalan, and . Tomkins, Extracting large-scale knowledge bases from the web, Proceedings of the 25th International Conference on Very Large Data Bases, VLDB '99, pp.639-650, 1999.

S. Kumar, M. Mohri, and A. Talwalkar, On sampling-based approximate spectral decomposition, Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp.553-560, 2009.
DOI : 10.1145/1553374.1553446

A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Physical Review E, vol.78, issue.4, 2008.
DOI : 10.1103/PhysRevE.78.046110

J. Leskovec and C. Faloutsos, Sampling from large graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '06, pp.631-636, 2006.
DOI : 10.1145/1150402.1150479

J. Leskovec, D. Huttenlocher, and J. Kleinberg, Signed networks in social media, Proceedings of the 28th international conference on Human factors in computing systems, CHI '10, 2010.
DOI : 10.1145/1753326.1753532

J. Leskovec, D. Huttenlocher, and J. Kleinberg, Predicting positive and negative links in online social networks, Proceedings of the 19th international conference on World wide web, WWW '10, 2010.
DOI : 10.1145/1772690.1772756

J. Leskovec, K. J. Lang, and M. Mahoney, Empirical comparison of algorithms for network community detection, Proceedings of the 19th international conference on World wide web, WWW '10, pp.631-640, 2010.
DOI : 10.1145/1772690.1772755

R. Don, A. T. Lick, and . White, k-degenerate graphs. Canad, J. Math, vol.22, pp.1082-1096, 1970.

H. Liu, E. Lim, H. W. Lauw, M. Le, A. Sun et al., Predicting trusts among users of online communities, Proceedings of the 9th ACM conference on Electronic commerce, EC '08, 2008.
DOI : 10.1145/1386790.1386838

T. Luczak, Size and connectivity of the k-core of a random graph

D. Luo, C. H. Ding, H. Huang, and F. Nie, Consensus spectral clustering in near-linear time, 2011 IEEE 27th International Conference on Data Engineering, pp.1079-1090, 2011.
DOI : 10.1109/ICDE.2011.5767925

S. Arun, T. Y. Maiya, and . Berger-wolf, Sampling community structure, WWW, pp.701-710, 2010.

S. Maniu, B. Cautis, and T. Abdessalem, Building a signed network from interactions in Wikipedia, Databases and Social Networks on, DBSocial '11, 2011.
DOI : 10.1145/1996413.1996417
URL : https://hal.archives-ouvertes.fr/hal-00703506

C. D. Manning, P. Raghavan, and H. Schütze, Introduction to information retrieval, 2008.
DOI : 10.1017/CBO9780511809071

W. David and . Matula, A min?max theorem for graphs with application to graph coloring, SIAM Reviews, vol.10, 1968.

D. W. Matula, G. Marble, and J. D. Isaacson, Graph coloring algorithms, Graph theory and computing, pp.109-122, 1972.

M. Mcglohon, L. Akoglu, and C. Faloutsos, Weighted graphs and disconnected components, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD 08, pp.524-532, 2008.
DOI : 10.1145/1401890.1401955

J. Balthrop, M. E. Newman, and S. Forrest, Email networks and the spread of computer viruses, Phys Rev E Stat Nonlin Soft Matter Phys, vol.66, 2002.

A. Mishra and A. Bhattacharya, Finding the bias and prestige of nodes in networks based on trust scores, Proceedings of the 20th international conference on World wide web, WWW '11, 2011.
DOI : 10.1145/1963405.1963485

J. Moody and D. R. White, Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups, American Sociological Review, vol.68, issue.1, pp.103-127, 2003.
DOI : 10.2307/3088904

M. E. Newman, Fast algorithm for detecting community structure in networks, Physical Review E, vol.69, issue.6, p.66133, 2004.
DOI : 10.1103/PhysRevE.69.066133

M. E. Newman and M. Girvan, Finding and evaluating community structure in networks, Physical Review E, vol.69, issue.2, 2004.
DOI : 10.1103/PhysRevE.69.026113

Y. Andrew, M. I. Ng, Y. Jordan, and . Weiss, On spectral clustering: Analysis and an algorithm, NIPS, pp.849-856, 2001.

S. Papadimitriou, J. Sun, C. Faloutsos, and P. S. Yu, Hierarchical, Parameter-Free Community Discovery, Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases -Part II, ECML PKDD '08, pp.170-187, 2008.
DOI : 10.1007/978-3-540-87481-2_12

B. Pittel, J. Spencer, and N. Wormald, Sudden Emergence of a Giantk-Core in a Random Graph, Journal of Combinatorial Theory, Series B, vol.67, issue.1, pp.111-151, 1996.
DOI : 10.1006/jctb.1996.0036

M. Polito and P. Perona, Grouping and dimensionality reduction by locally linear embedding, NIPS, pp.1255-1262, 2001.

B. Bollobá-s, O. Riordan, J. Spencer, and G. Tusnády, The degree sequence of a scale-free random graph process. random structures and algorithms, pp.279-290, 2001.

V. Satuluri and S. Parthasarathy, Scalable graph clustering using stochastic flows, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, pp.737-746, 2009.
DOI : 10.1145/1557019.1557101

V. Satuluri, S. Parthasarathy, and Y. Ruan, Local graph sparsification for scalable clustering, Proceedings of the 2011 international conference on Management of data, SIGMOD '11, pp.721-732
DOI : 10.1145/1989323.1989399

B. Stephen and . Seidman, Network structure and minimum degree, Social Networks, vol.5, issue.3, pp.269-287, 1983.

M. Serrano and M. Boguñá, Topology of the world trade web, Physical Review E, vol.68, issue.1, p.68, 2003.
DOI : 10.1103/PhysRevE.68.015101

J. Shi and J. Malik, Normalized cuts and image segmentation

M. Sozio and A. Gionis, The community-search problem and how to plan a successful cocktail party, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, pp.939-948, 2010.
DOI : 10.1145/1835804.1835923

G. Szekeres and H. S. Wilf, An inequality for the chromatic number of a graph, Journal of Combinatorial Theory, vol.4, issue.1, pp.1-3, 1968.
DOI : 10.1016/S0021-9800(68)80081-X

S. Wasserman, K. Faust, ]. D. Watts, and S. H. Strogatz, Social Networks Analysis: Methods and Applications. Cambridge Collective dynamics of'small-world'networks, Nature, vol.88, issue.6684, p.393, 1994.
DOI : 10.1017/CBO9780511815478

S. White and P. Smyth, A Spectral Clustering Approach To Finding Communities in Graphs, SDM, 2005.
DOI : 10.1137/1.9781611972757.25

S. Wuchty and E. Almaas, Peeling the yeast protein network, PROTEOMICS, vol.406, issue.2, pp.444-449, 2005.
DOI : 10.1002/pmic.200400962

D. Yan, L. Huang, and M. I. Jordan, Fast approximate spectral clustering, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, pp.907-916, 2009.
DOI : 10.1145/1557019.1557118
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.148.1997