Skip to main content
Erschienen in: Cluster Computing 3/2015

01.09.2015

GRAPPE : a system for determining optimal connecting route to target person based on mutual intimacy index

verfasst von: Kimun Keum, Sejin Nam, Yongho Kang, Ohseok Kwon

Erschienen in: Cluster Computing | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

Recently, the growth of social network service (SNS, Facebook) has required the search technique to utilize its distinctive characteristic which links people to people. This paper discusses the design and implementation of GRAPPE which suggests the ranked list of optimal connecting routes between two people by interaction like SNS, phone calls, texts, mails. It is based on mutual intimacy index (MII) which indicate how closely two people are related. MII is calculated periodically when a user interact with other person by smartphone. In this study, we propose a simple two-ended search method for finding optimal routes between a source person and a destination person. For the real-time service it searches optimal path within 3 step-away relationship in human network that is effective in real life while existing services in SNS usually provide one-ended search on entire paths. Furthermore, we also use the pruning technique for efficient execution time.

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!

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!

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!

Literatur
2.
Zurück zum Zitat Milgram, S.: The small world problem. Psychol. Today 2, 60–67 (1967) Milgram, S.: The small world problem. Psychol. Today 2, 60–67 (1967)
3.
Zurück zum Zitat Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature 393, 440–442 (1998)CrossRef Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature 393, 440–442 (1998)CrossRef
4.
Zurück zum Zitat Christakis, N.A., Fowler, J.H.: Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives. Back Bay Books, New York (2011) Christakis, N.A., Fowler, J.H.: Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives. Back Bay Books, New York (2011)
5.
Zurück zum Zitat Cheol-Min, L., Chang-Su, K., Kyung-Won, P., Hyun-Sook, A.: A study on business strategies and success factors of social network service and enterprises: focusing on representative SNS of Korea. J. Digit. Converg. 12(7), 177–187 (2014)CrossRef Cheol-Min, L., Chang-Su, K., Kyung-Won, P., Hyun-Sook, A.: A study on business strategies and success factors of social network service and enterprises: focusing on representative SNS of Korea. J. Digit. Converg. 12(7), 177–187 (2014)CrossRef
6.
Zurück zum Zitat Kyung-Ja, P., Seong-Joon, P., Hee-Young, J.: Study on the use of SNS (social network service) for tasks: focus on the task-media fit. J. Digit. Converg. 12(2), 577–586 (2014) Kyung-Ja, P., Seong-Joon, P., Hee-Young, J.: Study on the use of SNS (social network service) for tasks: focus on the task-media fit. J. Digit. Converg. 12(2), 577–586 (2014)
7.
Zurück zum Zitat Chen, L.-C., Kuo, P.-J., Liao, I.-E.: Ontology-based library recommender system using MapReduce. Clust. Comput. 18(1), 113–121 (2015)CrossRef Chen, L.-C., Kuo, P.-J., Liao, I.-E.: Ontology-based library recommender system using MapReduce. Clust. Comput. 18(1), 113–121 (2015)CrossRef
8.
Zurück zum Zitat Wu, J., Chen, L., Yu, Q., Kuang, L., Wang, Y., Wu, Z.: Selecting skyline services for QoS-aware composition by upgrading MapReduce paradigm. Clust. Comput. 6(4), 693–706 (2013)CrossRef Wu, J., Chen, L., Yu, Q., Kuang, L., Wang, Y., Wu, Z.: Selecting skyline services for QoS-aware composition by upgrading MapReduce paradigm. Clust. Comput. 6(4), 693–706 (2013)CrossRef
9.
Zurück zum Zitat Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 252001, 163–177 (2001)CrossRef Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 252001, 163–177 (2001)CrossRef
10.
Zurück zum Zitat van den Berg, P., Arentze, T., Timmermans, H.: A path analysis of social networks, telecommunication and social activity-travel patterns. Transp. Res. Part C 26, 256–268 (2013)CrossRef van den Berg, P., Arentze, T., Timmermans, H.: A path analysis of social networks, telecommunication and social activity-travel patterns. Transp. Res. Part C 26, 256–268 (2013)CrossRef
11.
Zurück zum Zitat Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Society for Industrial and Applied Mathematics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (2005) Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Society for Industrial and Applied Mathematics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (2005)
12.
Zurück zum Zitat Yoon-Su, J., Kun-Hee, H.: Big data processing scheme of distribution environment. J. Digit. Converg. 12(6), 311–316 (2014)CrossRef Yoon-Su, J., Kun-Hee, H.: Big data processing scheme of distribution environment. J. Digit. Converg. 12(6), 311–316 (2014)CrossRef
13.
Zurück zum Zitat Nam-Gue, P., Sun-Bae, K.: A proposal for SmartTV development plan by applying big data analysis methodology. J. Digit. Converg. 12(1), 347–358 (2014)CrossRef Nam-Gue, P., Sun-Bae, K.: A proposal for SmartTV development plan by applying big data analysis methodology. J. Digit. Converg. 12(1), 347–358 (2014)CrossRef
14.
Zurück zum Zitat Choi, K.-H., Oh, H.-H., Kwag, H.-J.: Network analysis using frequency of cross-citation and comparing citation index of accounting journals. J. Digit. Converg. 12(2), 143–149 (2014)CrossRef Choi, K.-H., Oh, H.-H., Kwag, H.-J.: Network analysis using frequency of cross-citation and comparing citation index of accounting journals. J. Digit. Converg. 12(2), 143–149 (2014)CrossRef
15.
Zurück zum Zitat Luo, J., Dong, F., Cao, J., Song, A.: A context-aware personalized resource recommendation for pervasive learning. Clust. Comput. 13(2), 13–39 (2010)CrossRef Luo, J., Dong, F., Cao, J., Song, A.: A context-aware personalized resource recommendation for pervasive learning. Clust. Comput. 13(2), 13–39 (2010)CrossRef
16.
Zurück zum Zitat Zhang, S., McCullagh, P., Zhang, J., Yu, T.: A smartphone based real-time daily activity monitoring system. Clust. Comput. 17, 1–11 (2013) Zhang, S., McCullagh, P., Zhang, J., Yu, T.: A smartphone based real-time daily activity monitoring system. Clust. Comput. 17, 1–11 (2013)
17.
Zurück zum Zitat Bellman, R.: On a routing problem. DTIC Doc. 16, 87–90 (1956) Bellman, R.: On a routing problem. DTIC Doc. 16, 87–90 (1956)
19.
Zurück zum Zitat Zhang, F., Jiping, L.: An algorithm of shortest path based on Dijkstra for huge data. In: Sixth International Conference on Fuzzy Systems and Knowledge Discovery 2009 (FSKD ’09), vol. 4, IEEE (2009) Zhang, F., Jiping, L.: An algorithm of shortest path based on Dijkstra for huge data. In: Sixth International Conference on Fuzzy Systems and Knowledge Discovery 2009 (FSKD ’09), vol. 4, IEEE (2009)
20.
Zurück zum Zitat Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)CrossRef Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)CrossRef
21.
Zurück zum Zitat Hart, P.E., et al.: A formal basis for the heuristic determination of minimum cost paths. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef Hart, P.E., et al.: A formal basis for the heuristic determination of minimum cost paths. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef
22.
Zurück zum Zitat Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1–13 (1977)CrossRefMATH Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1–13 (1977)CrossRefMATH
23.
Zurück zum Zitat Viterbi, A.J.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13(2), 260–269 (1967)CrossRefMATH Viterbi, A.J.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13(2), 260–269 (1967)CrossRefMATH
24.
Zurück zum Zitat Jinha, K., Seung-Keol, K., Hwanjo, Y.: Scalable and parallelizable processing of influence maximization for large-scale social networks. In: IEEE 29th International Conference on Data Engineering (ICDE), pp. 266–277 (2013) Jinha, K., Seung-Keol, K., Hwanjo, Y.: Scalable and parallelizable processing of influence maximization for large-scale social networks. In: IEEE 29th International Conference on Data Engineering (ICDE), pp. 266–277 (2013)
25.
Zurück zum Zitat Kourtellis, N., Alahakoon, T., Simha, R., Iamnitchi, A., Tripathi, R.: Identifying high betweenness centrality nodes in large social networks. Soc. Netw. Anal. Min. 3, 899–914 (2013)CrossRef Kourtellis, N., Alahakoon, T., Simha, R., Iamnitchi, A., Tripathi, R.: Identifying high betweenness centrality nodes in large social networks. Soc. Netw. Anal. Min. 3, 899–914 (2013)CrossRef
26.
Zurück zum Zitat Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Trans. Netw. 16(1), 25–36 (2008)CrossRef Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Trans. Netw. 16(1), 25–36 (2008)CrossRef
27.
Zurück zum Zitat Song, H.H., et al.: Clustered embedding of massive social networks. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems (2012) Song, H.H., et al.: Clustered embedding of massive social networks. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems (2012)
28.
Zurück zum Zitat Klodt, P., et al.: Indexing Strategies for Constrained Shortest Paths over Large Social Networks. Universitat des Saarlandes (2011) Klodt, P., et al.: Indexing Strategies for Constrained Shortest Paths over Large Social Networks. Universitat des Saarlandes (2011)
29.
Zurück zum Zitat Sarma, A. D., et al.: A sketch-based distance oracle for web-scale graphs.In: Proceedings of the third ACM international conference on Web search and data mining, 401–410 (2010) Sarma, A. D., et al.: A sketch-based distance oracle for web-scale graphs.In: Proceedings of the third ACM international conference on Web search and data mining, 401–410 (2010)
30.
Zurück zum Zitat Zhao, X., Sala, A., Wilson, C., Zheng, H., Zhao, B.Y.: Orion: shortest path estimation for large social graphs. WOSN’10 1, 1–9 (2010) Zhao, X., Sala, A., Wilson, C., Zheng, H., Zhao, B.Y.: Orion: shortest path estimation for large social graphs. WOSN’10 1, 1–9 (2010)
31.
Zurück zum Zitat Zhao, X., et al.: Efficient shortest paths on massive social graphs. In: 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), 2011. IEEE (2011) Zhao, X., et al.: Efficient shortest paths on massive social graphs. In: 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), 2011. IEEE (2011)
32.
Zurück zum Zitat Gubichev, A., T. Neumann: Path query processing on very large rdf graphs. In: Proceedings of the 14th International Workshop on the Web and Databases (WebDB) (2011) Gubichev, A., T. Neumann: Path query processing on very large rdf graphs. In: Proceedings of the 14th International Workshop on the Web and Databases (WebDB) (2011)
33.
Zurück zum Zitat Gubichev, A., et al.: Fast and accurate estimation of shortest paths in large graphs. In: Proceedings of the 19th ACM international conference on Information and knowledge management, ACM, 499–508 (2010) Gubichev, A., et al.: Fast and accurate estimation of shortest paths in large graphs. In: Proceedings of the 19th ACM international conference on Information and knowledge management, ACM, 499–508 (2010)
34.
Zurück zum Zitat Frank, E.: Pruning Decision Trees and Lists, PhD thesis, University of Waikato, Hamilton (2000) Frank, E.: Pruning Decision Trees and Lists, PhD thesis, University of Waikato, Hamilton (2000)
Metadaten
Titel
GRAPPE : a system for determining optimal connecting route to target person based on mutual intimacy index
verfasst von
Kimun Keum
Sejin Nam
Yongho Kang
Ohseok Kwon
Publikationsdatum
01.09.2015
Verlag
Springer US
Erschienen in
Cluster Computing / Ausgabe 3/2015
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-015-0458-4

Weitere Artikel der Ausgabe 3/2015

Cluster Computing 3/2015 Zur Ausgabe