nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

A Label Inference Method Based on Maximal Entropy Random Walk over Graphs

verfasst von : Jing Pan, Yajun Yang, Qinghua Hu, Hong Shi

Erschienen in: Web Technologies and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

With the rapid development of Internet, graphs have been widely used to model the complex relationships among various entities in real world. However, the labels on the graphs are always incomplete. The accurate label inference is required for many real applications such as personalized service and product recommendation. In this paper, we propose a novel label inference method based on maximal entropy random walk. The main idea is that a small number of vertices in graphs propagate their labels to other unlabeled vertices in a way of random walk with the maximal entropy guidance. We give the algorithm and analyze the time and space complexities. We confirm the effectiveness of our algorithm through conducting experiments on real datasets.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Feature Selection via Vectorizing Feature’s Discriminative Information

Nächstes Kapitel An Adaptive kNN Using Listwise Approach for Implicit Feedback

Azran, A.: The rendezvous algorithm: Multiclass semi-supervised learning with Markov random walks. In: Proceedings of the 24th International Conference on Machine Learning, pp. 49–56. ACM (2007)

Bhagat, S., Cormode, G., Muthukrishnan, S.: Node classification in social networks. In: Aggarwal, C.C. (ed.) Social Network Data Analytics, pp. 115–148. Springer, New York (2011)CrossRef

Burda, Z., Duda, J., Luck, J., Waclaw, B.: Localization of the maximal entropy random walk. Phys. Rev. Lett. 102(16), 160602 (2009)CrossRef

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)MathSciNetCrossRef

Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., Koutra, D., Faloutsos, C., Li, L.: Rolx: structural role extraction & mining in large graphs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1231–1239. ACM (2012)

Hu, X., Liu, H.: Social status and role analysis of Palin’s email network. In: Proceedings of the 21st International Conference Companion on World Wide Web, pp. 531–532. ACM (2012)

Jaakkola, M.S.T., Szummer, M.: Partially labeled classification with Markov random walks. In: Advances in Neural Information Processing Systems (NIPS), vol. 14, pp. 945–952 (2002)

Leuski, A.: Email is a stage: discovering people roles from email archives. In: Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 502–503. ACM (2004)

Li, R.H., Yu, J.X., Huang, X., Cheng, H.: Random-walk domination in large graphs. In: 2014 IEEE 30th International Conference on Data Engineering (ICDE), pp. 736–747. IEEE (2014)

10.

Li, R.H., Yu, J.X., Liu, J.: Link prediction: the power of maximal entropy random walk. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pp. 1147–1156. ACM (2011)

11.

Lovász, L., et al.: Random walks on graphs: a survey. Comb. Paul Erdos is Eighty 2, 353–398 (1996)MathSciNetMATH

12.

McCallum, A., Wang, X., Corrada-Emmanuel, A.: Topic and role discovery in social networks with experiments on enron and academic email. J. Artif. Intell. Res. 30, 249–272 (2007)

13.

McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: homophily in social networks. Ann. Rev. Sociol. 27, 415–444 (2001)CrossRef

14.

Mislove, A., Viswanath, B., Gummadi, K.P., Druschel, P.: You are who you know: inferring user profiles in online social networks. In: Proceedings of the Third ACM International Conference on Web Search and Data Mining, pp. 251–260. ACM (2010)

15.

Neville, J., Jensen, D.: Iterative classification in relational data. In: Proceedings of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data, pp. 13–20 (2000)

16.

Ribeiro, B., Wang, P., Murai, F., Towsley, D.: Sampling directed graphs with random walks. In: 2012 Proceedings IEEE INFOCOM, pp. 1692–1700. IEEE (2012)

17.

Wang, G., Zhao, Y., Shi, X., Yu, P.S.: Magnet community identification on social networks. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 588–596. ACM (2012)

18.

Welser, H.T., Cosley, D., Kossinets, G., Lin, A., Dokshin, F., Gay, G., Smith, M.: Finding social roles in Wikipedia. In: Proceedings of the 2011 iConference, pp. 122–129. ACM (2011)

19.

Xie, J., Szymanski, B.K.: Community detection using a neighborhood strength driven label propagation algorithm. In: 2011 IEEE Network Science Workshop (NSW), pp. 188–195. IEEE (2011)

20.

Zhao, Y., Sundaresan, N., Shen, Z., Yu, P.S.: Anatomy of a web-scale resale market: a data mining approach. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1533–1544. International World Wide Web Conferences Steering Committee (2013)

21.

Zhao, Y., Wang, G., Yu, P.S., Liu, S., Zhang, S.: Inferring social roles and statuses in social networks. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 695–703. ACM (2013)

22.

Zheleva, E., Getoor, L.: To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles. In: Proceedings of the 18th International Conference on World Wide Web, pp. 531–540. ACM (2009)

23.

Zhu, X., Ghahramani, Z., Lafferty, J., et al.: Semi-supervised learning using Gaussian fields and harmonic functions. In: ICML, vol. 3, pp. 912–919 (2003)

Titel: A Label Inference Method Based on Maximal Entropy Random Walk over Graphs
verfasst von: Jing Pan
Yajun Yang
Qinghua Hu
Hong Shi
Verlag: Springer International Publishing
Buch: Web Technologies and Applications
Print ISBN: 978-3-319-45813-7

Electronic ISBN: 978-3-319-45814-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-45814-4_41

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"