Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-24T05:38:55.242Z Has data issue: false hasContentIssue false
  • English
  • Français

The small-community phenomenon in networks†

Published online by Cambridge University Press:  06 March 2012

ANGSHENG LI  and
PAN PENG
ANGSHENG LI
Affiliation:
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100190, P.R. China Email: [email protected]
PAN PENG*
Affiliation:
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100190, P.R. China and School of Information Science and Engineering, Graduate University of China Academy of Sciences, P.R. China Email: [email protected].
*
§Corresponding author.
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate several geometric models of networks that simultaneously have some nice global properties, including the small-diameter property, the small-community phenomenon, which is defined to capture the common experience that (almost) everyone in society also belongs to some meaningful small communities, and the power law degree distribution, for which our result significantly strengthens those given in van den Esker (2008) and Jordan (2010). These results, together with our previous work in Li and Peng (2011), build a mathematical foundation for the study of both communities and the small-community phenomenon in various networks.

In the proof of the power law degree distribution, we develop the method of alternating concentration analysis to build a concentration inequality by alternately and iteratively applying both the sub- and super-martingale inequalities, which seems to be a powerful technique with further potential applications.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 22 , Issue 3 , June 2012 , pp. 373 - 407
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

This research was partially supported by NSFC distinguished young investigator award number 60325206, and its matching fund from the Hundred-Talent Program of the Chinese Academy of Sciences. Both authors are partially supported by the Grand Project ‘Network Algorithms and Digital Information’ of the Institute of Software, Chinese Academy of Sciences.

References

Albert, R., Jeong, H. and Barabási, A.-L. (1999) The diameter of the World Wide Web. Nature 401 130–131.Google Scholar
Allen, C. (2004) Life with alacrity: The dunbar number as a limit to group sizes. Available at http://www.lifewithalacrity.com/2004/03/the_dunbar_numb.html.Google Scholar
Avin, C. (2008) Distance graphs: from random geometric graphs to Bernoulli graphs and between. In: Proceedings of the fifth international workshop on Foundations of mobile computing 71–78.Google Scholar
Bollobás, B. (2001) Random Graphs (second edition), Cambridge University Press.Google Scholar
Bollobás, B. (2003) Mathematical results on scale-free random graphs. In: In Handbook of Graphs and Networks, Wiley-VCH 1–34.Google Scholar
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. and Wiener, J. (2000) Graph structure in the web. Computer Networks 33 (1–6)309–320.Google Scholar
Chung, F. and Lu, L. (2004) The small world phenomenon in hybrid power law graphs. In: Ben-Naim, E. et al. (eds.) Complex Networks, Springer-Verlag 91–106.Google Scholar
Chung, F. and Lu, L. (2006) Complex Graphs and Networks (CBMS Regional Conference Series in Mathematics), American Mathematical Society.Google Scholar
Devroye, L. and Lu, J. (1995) The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures and Algorithms 7 1–14.Google Scholar
Dubhashi, D. and Panconesi, A. (2009) Concentration of Measure for the Analysis of Randomized Algorithms (first edition), Cambridge University Press.Google Scholar
Flaxman, A. D., Frieze, A. M. and Vera, J. (2007a) A geometric preferential attachment model of networks. Internet Mathematics 3 (2)187–205.Google Scholar
Flaxman, A. D., Frieze, A. M. and Vera, J. (2007b) A geometric preferential attachment model of networks II. Internet Mathematics 4 (1)87–111.Google Scholar
Fraigniaud, P. and Giakkoupis, G. (2009) The effect of power-law degrees on the navigability of small worlds [extended abstract]. In: Proceedings of the 28th ACM symposium on Principles of distributed computing: PODC '09, ACM 240–249.Google Scholar
Groh, G. and Rappel, V. (2009) Towards demarcation and modeling of small sub-communities/groups in p2p social networks. In: CSE '09: Proceedings of the 2009 International Conference on Computational Science and Engineering, IEEE Computer Society 304–311.Google Scholar
Horton, D. and Wohl, R. R. (1956) Mass communication and para-social interaction: Observations on intimacy at a distance. Psychiatry 19 (3)215–229.Google Scholar
Jordan, J. (2010) Degree sequences of geometric preferential attachment graphs. Advances in Applied Probability 42 319–330.Google Scholar
Kannan, R., Vempala, S. and Vetta, A. (2004) On clusterings: Good, bad and spectral. Journal of the ACM 51 (3)497–515.CrossRefGoogle Scholar
Kleinberg, J. (2000) The small-world phenomenon: an algorithmic perspective. In: Proceedings of the 32nd ACM Symposium on the Theory of Computing.Google Scholar
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S. and Tomkins, A. S. (1999) The Web as a graph: measurements, models and methods. In: Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON). Springer-Verlag Lecture Notes in Computer Science 1627 1–18.Google Scholar
Kurucz, M. and Benczúr, A. A. (2010) Geographically organized small communities and the hardness of clustering social networks. Annals of Information Systems – Data Mining for Social Network Analyis.Google Scholar
Lang, K. (2005) Fixing two weaknesses of the spectral method. In: NIPS '05. Advances in Neural Information Processing Systems 18.Google Scholar
Leskovec, J., Lang, K. J., Dasgupta, A. and Mahoney, M. W. (2008) Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. (Informal publication: CoRR abs/0810.1355.)Google Scholar
Leskovec, J., Lang, K. J. and Mahoney, M. (2010) Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th international conference on World wide web: WWW '10, ACM 631–640.Google Scholar
Li, A. and Peng, P. (2011) Communities structures in classical network models. Internet Mathematics 7 (2)81–106.Google Scholar
Penrose, M. (2003) Random Geometric Graphs, Oxford University Press.Google Scholar
Pittel, B. (1994) Note on the heights of random recursive trees and random m-ary search trees. Random Structures and Algorithms 5 337–347.Google Scholar
Ravasz, E. and Barabási, A.-L. (2003) Hierarchical organization in complex networks. Physical Review E 67 026112.Google Scholar
Smythe, R. and Mahmoud, H. (1995) A survey of recursive trees. Theory of Probability and Mathematical Statistics 51 1–27.Google Scholar
van den Esker, H. (2008) A geometric preferential attachment model with fitness. (Available at http://arxiv.org/abs/0801.1612.)Google Scholar