K. Avrachenkov and N. Litvak, The Effect of New Links on Google Pagerank, Stochastic Models, vol.22, issue.2, pp.319-331, 2006.
DOI : 10.1080/15427951.2004.10129091
URL : https://hal.archives-ouvertes.fr/inria-00070742

L. Backstrom and J. Leskovec, Supervised random walks, Proceedings of the fourth ACM international conference on Web search and data mining, WSDM '11, pp.635-644, 2011.
DOI : 10.1145/1935826.1935914

A. Barabasi and R. Albert, Emergence of scaling in random networks, Science, vol.286, issue.5439, pp.509-512, 1999.

R. Bauer, D. Gianlorenzo, D. Angelo, A. Delling, D. Schumm et al., The Shortcut Problem - Complexity and Algorithms, Journal of Graph Algorithms and Applications, vol.16, issue.2, pp.447-481, 2012.
DOI : 10.7155/jgaa.00270
URL : https://hal.archives-ouvertes.fr/hal-00728877

A. Edward, E. R. Bender, and . Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Comb. Theory Ser. A, vol.24, issue.3, pp.296-307, 1978.

L. Davidebiì-o, G. Guaì, and . Proietti, Improved approximability and non-approximability results for graph diameter decreasing problems, Theor. Comput. Sci, vol.417, pp.12-22, 2012.

P. Boldi and S. Vigna, Axioms for Centrality, Internet Mathematics, vol.10, issue.3-4, pp.3-4, 2014.
DOI : 10.1080/15427951.2013.865686

B. Bollobásbollob´bollobás, C. Borgs, J. Chayes, and O. Riordan, Directed scale-free graphs, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03). SIAM, pp.132-139, 2003.

F. Chierichetti, R. Kumar, S. Lattanzi, A. Panconesi, and P. Raghavan, Models for the compressible web, Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS'09, pp.331-340, 2009.
DOI : 10.1109/focs.2009.63
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.185.906

E. Cohen, D. Delling, T. Pajor, and R. F. Werneck, Computing classic closeness centrality, at scale, Proceedings of the second edition of the ACM conference on Online social networks, COSN '14, 2014.
DOI : 10.1145/2660460.2660465
URL : http://arxiv.org/pdf/1409.0035

P. Crescenzi, D. Gianlorenzo, L. Angelo, Y. Severini, and . Velaj, Greedily Improving Our Own Centrality in A Network, Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15, pp.43-55, 2015.
DOI : 10.1007/978-3-319-20086-6_4
URL : https://hal.archives-ouvertes.fr/hal-01248558

D. Gianlorenzo, L. Angelo, Y. Severini, and . Velaj, On the maximum betweenness improvement problem, Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS'15), pp.153-168, 2016.

S. Dehghani, M. Amin-fazli, J. Habibi, and S. Yazdanbod, Using shortcut edges to maximize the number of triangles in graphs, Operations Research Letters, vol.43, issue.6, p.6, 2015.
DOI : 10.1016/j.orl.2015.09.003

E. D. Demaine and M. Zadimoghaddam, Minimizing the Diameter of a Network Using Shortcut Edges, Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'10, pp.420-431, 2010.
DOI : 10.1007/978-3-642-13731-0_39

I. Dinur and D. Steurer, Analytical approach to parallel repetition, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.624-633, 2014.
DOI : 10.1007/978-3-642-15369-3_54
URL : http://arxiv.org/abs/1305.1979

A. Erd?-os and . Rényi, On random graphs I, Publ. Math, vol.6, pp.290-297, 1959.

U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM, vol.45, issue.4, 1998.
DOI : 10.1145/285055.285059

F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson, Augmenting Graphs to Minimize the Diameter, Algorithmica, vol.11, issue.1, pp.995-1010, 2015.
DOI : 10.1002/jgt.3190110315
URL : http://arxiv.org/abs/1309.5172

V. Ishakian, D. Erdös, E. Terzi, and A. Bestavros, A Framework for the Evaluation and Management of Network Centrality, Proceedings of the 12th SIAM Int. Conf. on Data Mining (SDM), 2012.
DOI : 10.1137/1.9781611972825.37

M. Kas, M. Wachs, K. M. Carley, and L. R. Carley, Incremental algorithm for updating betweenness centrality in dynamically growing networks, Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM '13, pp.33-40, 2013.
DOI : 10.1145/2492517.2492533

D. Kempe and J. Kleinberg, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '03, pp.105-147, 2015.
DOI : 10.1145/956750.956769

R. Kumar, P. Raghavan, D. Sridhar-rajagopalan, A. Sivakumar, E. Tomkins et al., Stochastic models for the Web graph, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.57-65, 2000.
DOI : 10.1109/SFCS.2000.892065
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.478

J. Kunegis, KONECT ? The Koblenz network collection, Proceedings of the 1st International Web Observatory Workshop (WOW'13, pp.1343-1350, 2013.

J. Leskovec, J. Kleinberg, and C. Faloutsos, Graph evolution, ACM Transactions on Knowledge Discovery from Data, vol.1, issue.1, 2007.
DOI : 10.1145/1217299.1217301

J. Leskovec and A. Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, 2014.

R. Li, J. Xu, and Y. , Triangle minimization in large networks, Knowledge and Information Systems, vol.23, issue.9, pp.617-643, 2015.
DOI : 10.1038/30918

D. Liben-nowell and J. Kleinberg, The link prediction problem for social networks, Proceedings of the 12th International Conference on Information and Knowledge Management (CIKM'03). ACM, pp.556-559, 2003.
DOI : 10.1145/956958.956972
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.6528

A. Meyerson and B. Tagiku, Minimizing Average Shortest Path Distances via Shortcut Edge Addition, Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'09, pp.272-285, 2009.
DOI : 10.1007/978-3-642-03685-9_21
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.5015

M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, vol.3, issue.2-3, pp.2-3, 1995.
DOI : 10.1002/rsa.3240030202

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions?I, Mathematical Programming, vol.16, issue.1, pp.265-294, 1978.
DOI : 10.1007/BF01588971

M. Olsen and A. Viglas, On the approximability of the link building problem, Theoretical Computer Science, vol.518, pp.96-116, 2014.
DOI : 10.1016/j.tcs.2013.08.003

C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol.43, issue.3, pp.425-440, 1991.
DOI : 10.1016/0022-0000(91)90023-X

M. Papagelis, Refining Social Graph Connectivity via Shortcut Edge Addition, ACM Transactions on Knowledge Discovery from Data, vol.10, issue.2, p.12, 2015.
DOI : 10.1145/1374376.1374389

M. Papagelis, F. Bonchi, and A. Gionis, Suggesting ghost edges for a smaller world, Proceedings of the 20th ACM international conference on Information and knowledge management, CIKM '11, pp.2305-2308, 2011.
DOI : 10.1145/2063576.2063952

N. Parotsidis, E. Pitoura, and P. Tsaparas, Selecting Shortcuts for a Smaller World, Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, pp.28-36, 2015.
DOI : 10.1137/1.9781611974010.4

N. Parotsidis, E. Pitoura, and P. Tsaparas, Centrality-Aware Link Recommendations, Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, WSDM '16, pp.503-512, 2016.
DOI : 10.1109/ASONAM.2010.27

S. Perumal, P. Basu, and Z. Guan, Minimizing Eccentricity in Composite Networks via Constrained Edge Additions, MILCOM 2013, 2013 IEEE Military Communications Conference, pp.1894-1899, 2013.
DOI : 10.1109/MILCOM.2013.319
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.645.5563

A. Popescul and L. H. Ungar, Statistical relational learning for link prediction, Proceedings of IJCAI Workshop on Learning Statistical Models from Relational Data, 2003.

S. Saha, A. Adiga, B. A. Prakash, A. Kumar, and S. Vullikanti, Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread, Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, pp.568-576, 2015.
DOI : 10.1137/1.9781611974010.64

A. Erdem-sariyücesariy¨sariyüce, K. Kaya, E. Saule, and V. , Incremental algorithms for closeness centrality, Proceedings of the 2013 IEEE International Conference on Big Data. IEEE, pp.487-492, 2013.

H. Tong, B. A. Prakash, and T. Eliassi-rad, Michalis Faloutsos, and Christos Faloutsos. 2012. Gelling, and melting, large graphs by edge manipulation, Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM'12, pp.245-254

J. Duncan, S. H. Watts, and . Strogatz, Collective dynamics of 'small-world' networks, Nature, vol.393, issue.6684, pp.440-442, 1998.

E. Yan and Y. Ding, Applying centrality measures to impact analysis: A coauthorship network analysis, Journal of the American Society for Information Science and Technology, vol.42, issue.1, pp.2107-2118, 2009.
DOI : 10.1017/CBO9780511815478
URL : http://arxiv.org/abs/1012.4862

Z. Yin, M. Gupta, T. Weninger, and J. Han, A Unified Framework for Link Recommendation Using Random Walks, 2010 International Conference on Advances in Social Networks Analysis and Mining, pp.152-159, 2010.
DOI : 10.1109/ASONAM.2010.27
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.514