nach oben

Data Mining and Knowledge Discovery

Erschienen in:

01.01.2016

Link prediction using time series of neighborhood-based node similarity scores

verfasst von: İsmail Güneş, Şule Gündüz-Öğüdücü, Zehra Çataltepe

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We propose a link prediction method for evolving networks. Our method first computes a number of different node similarity scores (e.g. Common Neighbor, Preferential Attachment, Adamic–Adar, Jaccard) and their weighted versions, for different past time periods. In order to predict the future node similarity scores, a powerful time series forecasting model, ARIMA, based on these past node similarity scores is used. This time series forecasting based approach enables link prediction based on modeling of the change of past node similarities and also external factors. The proposed link prediction method can be used for evolving networks and prediction of new or recurring links. We evaluate the link prediction performances of our proposed method and the previously proposed time series and similarity based link prediction methods under different circumstances by means of different AUC measures. We show that, the link prediction method proposed in this article results in a better performance than the previous methods.

Vorheriger Artikel On detecting maximal quasi antagonistic communities in signed graphs

Nächster Artikel Sampling frequent and minimal boolean patterns: theory and application in classification

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

Acar E, Dunlavy DM, Kolda TG (2009) Link prediction on evolving data using matrix and tensor factorizations. In: ICDM Workshops. IEEE Computer Society, New York, pp 262–269

Adamic L, Adar E (2003) Friends and neighbors on the web. Soc Netw 25(20):211–230CrossRef

Akaike H (1974) A new look at the statistical model identification. IEEE Trans Autom Control 19(6):716–723MATHMathSciNetCrossRef

Amjady N (2001) Short-term hourly load forecasting using time-series modeling with peak load estimation capability. IEEE Trans Power Syst 16(3):498–505CrossRef

Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D-U (2006) Complex networks: structure and dynamics. Phys Rep 424(4–5):175–308MathSciNetCrossRef

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30(17):107–117CrossRef

Brockwell P, Davis R (1991) Time series, 2nd edn. Springer series in statistics. Springer, New York

Chen AC-L, Gao S, Karampelas P, Alhajj R, Rokne JG (2011) Finding hidden links in terrorist networks by checking indirect links of different sub-networks. In: Wiil UK (ed) Counterterrorism and open source intelligence, vol 2., Lecture Notes in Social Networks. Springer, Berlin, pp 143–158

Da Silva Soares PR, Prudencio RBC (2012) Time series based link prediction. In: The 2012 international joint conference on neural networks (IJCNN). IEEE, New York, pp 1–7

Da Silva Soares PR, Prudencio RBC (2013) Proximity measures for link prediction based on temporal events. Exp Syst Appl 40(16):6652–6660CrossRef

Erdős P, Renyi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17

Espinoza M, Joye C, Belmans R, DeMoor B (2005) Short-term load forecasting, profile identification, and customer segmentation: a methodology based on periodic time series. IEEE Trans Power Syst 20(3):1622–1630CrossRef

Getoor L, Diehl CP (2005) Link mining: a survey. ACM SIGKDD Explor Newsl 7(2):3–12CrossRef

Güneş İ, Çataltepe Z, Gündüz-Öğüdücü Ş (2014) Ga-tvrc-het: genetic algorithm enhanced time varying relational classifier for evolving heterogeneous networks. Data Min Knowl Discov 28:670–701MathSciNetCrossRef

Hasan MA, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning. In: Proceedings of SDM 06 workshop on link analysis, counterterrorism and security

Hsu WH, King AL, Paradesi MSR, Pydimarri T, Weninger T (2006) Collaborative and structural recommendation of friends using weblog-based social network analysis. In: AAAI spring symposium on computational approaches to analyzing weblogs. AAAI, pp 55–60

Hsu WH, Weninger T, Paradesi MSR (2008) Predicting links and link change in friends networks: supervised time series learning with imbalanced data. In: Proceedings of articial neural networks in engineering

Huang Z, Li X, Chen H (2005) Link prediction approach to collaborative filtering. In: Proceedings of the 5th ACM/IEEE-CS joint conference on digital libraries, JCDL ’05. ACM, New York, pp. 141–142

Huang Z, Lin DKJ (2009) The time-series link prediction problem with applications in communication surveillance. INFORMS J Comput 21(2):286–303CrossRef

Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43MATHCrossRef

Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining. ACM, New York, pp 177–187

Liben-Nowell D, Kleinberg JM (2007) The link-prediction problem for social networks. JASIST 58(7):1019–1031CrossRef

Lichtenwalter RN, Lussier JT, Chawla NV (2010) New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’10. ACM, New York, pp 243–252

Liu Z, Zhang Q-M, Lu L, Zhou T (2011) Link prediction in complex networks: a local nave bayes model, CoRR arXiv:1105.4005

Lü L, Jin C, Zhou T (2009) Similarity index based on local paths for link prediction of complex networks. Phys Rev E 80(4):046122CrossRef

Lü L, Zhou T (2010) Link prediction in weighted networks: the role of weak ties. EPL (Europhys Lett) 89:18001CrossRef

Lu L, Zhou T (2011) Link prediction in complex networks: a survey. Phys A 390(6):11501170MathSciNetCrossRef

Mitzenmacher M (2004) A brief history of generative models for power law and lognormal distributions. Internet Math 1(2):226–251MATHMathSciNetCrossRef

Moreno Y, Pastor-Satorras R, Vespignani A (2002) Epidemic outbreaks in complex heterogeneous networks. Eur Phys J B 26(4):521–529

Murata T, Moriyasu S (2007) Link prediction of social networks based on weighted proximity measures. In: Proceedings of the IEEE/WIC/ACM international conference on web intelligence, WI ’07. IEEE Computer Society, Washington, pp 85–88

Newman M (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102CrossRef

O’Madadhain J, Hutchins J, Smyth P (2005) Prediction and ranking algorithms for event-based network data. SIGKDD Explor Newsl 7(2):23–30CrossRef

Onnela J-P, Saramäki J, Hyvönen J, Szabó G, Lazer D, Kaski K, Kertész J, Barabási A-L (2007) Structure and tie strengths in mobile communication networks. Proc Natl Acad Sci 104(18):7332–7336CrossRef

Potgieter A, April A, Cooke RJ, Osunmakinde IO (2009) Temporality in link prediction: wnderstanding social complexity. Emergence 11(1):68–93

Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D (2004) Defining and identifying communities in networks. PNAS 101(9):2658–2663CrossRef

Salton G, McGill M (1983) Introduction to modern information retrieval. McGraw-Hill, New YorkMATH

Schifanella R, Barrat A, Cattuto C, Markines B, Menczer F (2010) Folks in Folksonomies: social link prediction from shared metadata, In: Proceedings of the third ACM international conference on Web search and data mining, WSDM ’10. ACM, New York, pp 271–280. doi:10.1145/1718487.1718521

Spiegel S, Clausen JH, Albayrak S, Kunegis J (2011) Link prediction on evolving data using tensor factorization. In: Cao L, Huang JZ, Bailey J, Koh YS, Luo J (eds) PAKDD Workshops. Lecture Notes in Computer Science, vol 7104. Springer, Berlin, pp 100–110

Taylor S (2007) Modelling financial time series, 2nd edn. World Scientific, SingaporeCrossRef

Tylenda T, Angelova R, Bedathur SJ (2009) Towards time-aware link prediction in evolving social networks. In: Giles CL, Mitra P, Perisic I, Yen J, Zhang H (eds) SNAKDD. ACM, New York, p 9

Wang C, Satuluri V, Parthasarathy S (2007) Local probabilistic models for link prediction. In: ICDM. IEEE Computer Society, New York, pp 322–331

Wilcoxon F (1945) Individual comparisons by ranking methods. Biomet Bull 1:80–83CrossRef

Xie X (2010) Potential friend recommendation in online social network. In: Green computing and communications (GreenCom), 2010 IEEE/ACM Int’l conference on & Int’l conference on cyber, physical and social computing (CPSCom). IEEE, New York, pp 831–835

Zhu J, Hong J, Hughes JG (2002) Using markov models for web site link prediction. In: Blustein J, Allen RB, Anderson KM, Moulthrop S (eds) Hypertext. ACM, New York, pp 169–170

Titel: Link prediction using time series of neighborhood-based node similarity scores
verfasst von: İsmail Güneş
Şule Gündüz-Öğüdücü
Zehra Çataltepe
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Data Mining and Knowledge Discovery / Ausgabe 1/2016
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-015-0407-0

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"

Weitere Artikel der Ausgabe 1/2016

Exceptional Model Mining

Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and tucker decompositions

On detecting maximal quasi antagonistic communities in signed graphs

Accelerating the discovery of unsupervised-shapelets

Sampling frequent and minimal boolean patterns: theory and application in classification

A computational approach inspired by simulated annealing to study the stability of protein interaction networks in cancer and neurological disorders