Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Meta Paths and Meta Structures: Analysing Large Heterogeneous Information Networks Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Counting Edges and Triangles in Online Social Networks via Random Walk

Authors : Yang Wu, Cheng Long, Ada Wai-Chee Fu, Zitong Chen

Published in: Web and Big Data

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Online social network (OSN) analysis has attracted much attention in recent years. Edge and triangle counts are both fundamental properties in OSNs. However, for many OSNs, one can only access parts of the network using the application programming interfaces (APIs). In such cases, conventional algorithms become infeasible. In this paper, we introduce efficient algorithms for estimating the number of edges and triangles in OSNs based on random walk sampling on OSNs. We also derive a theoretical bound on the sample size and number of APIs calls needed in our algorithms for a probabilistic accuracy guarantee. We ran experiments on several publicly available real-world networks and the results demonstrate the effectiveness of our algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Detecting User Occupations on Microblogging Platforms: An Experimental Study
next chapter Fair Reviewer Assignment Considering Academic Social Network
Appendix
Available only for authorised users
Literature
1.
Katzir, L., Liberty, E., Somekh, O.: Estimating sizes of social networks via biased sampling. In: WWW, pp. 597–606 (2011)
2.
Hardiman, S.J., Katzir, L.: Estimating clustering coefficients and size of social networks via random walk. In: WWW, pp. 539–550 (2013)
3.
Jha, M., Seshadhri, C., Pinar, A.: Path sampling: a fast and provable method for estimating 4-vertex subgraph counts. In: WWW, pp. 495–505 (2015)
4.
Lee, C.-H., Xu, X., Eun, D.Y.: Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling. In: SIGMETRICS, pp. 319–330 (2012)
5.
Li, R.-H., Yu, J., Qin, L., Mao, R., Jin, T.: On random walk based graph sampling. In: ICDE, pp. 927–938 (2015)
6.
Wang, P., Lui, J.C.S., Ribeiro, B., Towsley, D., Zhao, J., Guan, X.: Efficiently estimating motif statistics of large networks. In: ICDE, pp. 8:1–8:27 (2014)
7.
Bhuiyan, M., Rahman, M., Al Hasan, M.: Guise: uniform sampling of graphlets for large graph analysis. In: ICDM, pp. 91–100 (2012)
8.
Seshadhri, C., Pinar, A., KoldaWedge, T.G.: Sampling for computing clustering coefficients and triangle counts on large graphs. Stat. Anal. Data Mining 7(4), 233–235 (2014)MathSciNetCrossRef
9.
Gjoka, M., Kurant, M., Butts, C.T.: Walking in Facebook: a case study of unbiased sampling of OSNs. In: INFOCOM, pp. 1–9 (2010)
10.
Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: KDD, pp. 16–24 (2008)
11.
Eckmann, J.-P., Moses, E.: Curvature of co-links uncovers hidden thematic layers in the World Wide Web. In: PNAS, pp. 5825–5829 (2002)
12.
13.
Berry, J.W., Fosvedt, L., Nordman, D., Phillips, C.A., Wilson, A.G.: Listing triangles in expected linear time on power law graphs with exponent at least 7/3. Technical report SAND 2010–4474C (2011)
14.
Chu, S., Cheng, J.: Triangle listing in massive networks and its applications. In: KDD, pp. 672–680 (2011)
15.
Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoret. Comput. Sci. 407, 458–473 (2008)MathSciNetCrossRefMATH
16.
Tsourakakis, C.E., Kang, U., Miller, G.L., Faloutsos, C.: Doulion: counting triangles in massive graphs with a coin. In: KDD, pp. 837–846 (2009)
17.
Chen, X., Li, Y., Wang, G.P., Lui, J.C.S.: A general framework for estimating graphlet statistics via random walk. CoRR abs/1603.07504 (2016)
18.
Park, H.-M., Silvestri, F., Kang, U., Pagh, R.: MapReduce triangle enumeration with guarantees. In: ACM Conference Information Knowledge Manage, pp. 1739–1748 (2014)
19.
Suri, S., Vassilvitskii, S.: Counting triangles and the curse of the last reducer. In: WWW, pp. 607–614 (2011)
20.
21.
Hu, X., Tao, Y., Chung, C.-W.: Massive graph triangulation. In: SIGMOD, pp. 325–336 (2013)
22.
Chu, S., Cheng, J.: Triangle listing in massive networks. ACM Trans. Knowl. Discov. Data 6(4), 17 (2012)CrossRef
23.
Pagh, R., Silvestri, F.: The input/output complexity of triangle enumeration. In: ACM Symposium Principles Database System, pp. 224–233 (2014)
24.
Seshadhri, C., Pinar, A., Kold, T.G.: Triadic measures on graphs: the power of wedge sampling. In: SDM (2013)
25.
Berry, J.W., Hendrickson, B., LaViolette, R.A., Phillips, C.A.: Tolerating the community detection resolutionlimit with edge weighting. Phys. Rev. E 83, 056119 (2011)CrossRef
26.
27.
28.
Metadata
Title
Counting Edges and Triangles in Online Social Networks via Random Walk
Authors
Yang Wu
Cheng Long
Ada Wai-Chee Fu
Zitong Chen
Copyright Year
2017
Book
Web and Big Data

Print ISBN: 978-3-319-63578-1

Electronic ISBN: 978-3-319-63579-8

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63579-8_27

Premium Partner

    Image Credits