Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
International Journal of Data Science and Analytics
Erschienen in: International Journal of Data Science and Analytics 2/2018

20.06.2018 | Regular Paper

On spectral analysis of directed signed graphs

verfasst von: Yuemeng Li, Shuhan Yuan, Xintao Wu, Aidong Lu

Erschienen in: International Journal of Data Science and Analytics | Ausgabe 2/2018

Einloggen

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

search-config
loading …

Abstract

It has been shown that the adjacency eigenspace of a network contains key information of its underlying structure. However, there has been no study on spectral analysis of the adjacency matrices of directed signed graphs. In this paper, we derive theoretical approximations of spectral projections from such directed signed networks using matrix perturbation theory. We use the derived theoretical results to study the influences of negative intra-cluster and inter-cluster directed edges on node spectral projections. We then develop a spectral clustering-based graph partition algorithm, SC-DSG, and conduct evaluations on both synthetic and real datasets. We compare SC-DSG with state-of-the-art spectral clustering methods and signed network embedding methods. Both theoretical analysis and empirical evaluation demonstrate the effectiveness of the proposed algorithm.
Vorheriger Artikel A characterization of sample selection bias in system evaluation and the case of information retrieval

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
Fußnoten
Literatur
1.
Agovic, A., Banerjee, A., Ganguly, A.R., Protopopescu, V.: Anomaly detection in transportation corridors using manifold embedding. In: Knowledge Discovery from Sensor Data, pp. 81–105 (2008)
2.
Anchuri, P., Magdon-Ismail, M.: Communities and balance in signed networks: a spectral approach. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE, pp. 235–242 (2012)
3.
Aouchiche, M., Hansen, P.: A survey of automated conjectures in spectral graph theory. Linear Algebra Appl. 432(9), 2293–2322 (2010)MathSciNetCrossRefMATH
4.
Arenas, A., Duch, J., Fernandez, A., Gomez, S.: Size reduction of complex networks preserving modularity. New J. Phys. 9, 176 (2007)MathSciNetCrossRef
5.
Azar, Y., Fiat, A., Karlin, A., McSherry, F., Saia, J.: Spectral analysis of data. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, ACM, pp. 619–626 (2001)
6.
Cao, S., Lu, W., Xu, Q.: Deep neural networks for learning graph representations. In: AAAI (2016)
7.
8.
Chiang, K.Y., Whang, J.J., Dhillon, I.S.: Scalable clustering of signed networks using balance normalized cut. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, ACM, pp. 615–624 (2012)
9.
10.
11.
Cvetkovic, D., Doob, M., Sachs, H.: Spectra of Graphs-theory and Applications, 3rd edn. Johan Ambrosius Bart Verlag, Heidelberg (1995)MATH
12.
13.
Friedland, S.: On an inverse problem for nonnegative and eventually nonnegative matrices. Israel J. Math. 29(1), 43–60 (1978)MathSciNetCrossRefMATH
14.
Frobenius, G.F., Frobenius, F.G., Frobenius, F.G., Frobenius, F.G., Mathematician, G.: Über Matrizen aus nicht negativen Elementen. Königliche Akademie der Wissenschaften (1912)
15.
Golub, G.H., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, Baltimore (1996)MATH
16.
Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: KDD (2016)
17.
18.
Heider, F.: Attitudes and cognitive organization. J. Psychol. 21(1), 107–112 (1946)CrossRef
19.
Hu, X., Lu, A., Wu, X.: Spectrum-based network visualization for topology analysis. IEEE Comput. Graph. Appl. 33(1), 58–68 (2013)CrossRef
20.
Hu, X., Wu, L., Lu, A., Wu, X.: Block-organized topology visualization for visual exploration of signed networks. In: IEEE International Conference on Data Mining Workshop, ICDMW 2015, Atlantic City, NJ, USA, November 14–17, 2015, pp. 652–659 (2015)
21.
Idé, T., Kashima, H.: Eigenspace-based anomaly detection in computer systems. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 440–449 (2004)
22.
Inohara, T.: Characterization of clusterability of signed graph in terms of newcombs balance of sentiments. Appl. Math. Comput. 133, 93–104 (2002)MathSciNetMATH
23.
Jean, S., Cho, K., Memisevic, R., Bengio, Y.: On using very large target vocabulary for neural machine translation. arXiv:​1412.​2007 [cs] (2014)
24.
Kim, J., Park, H., Lee, J.E., Kang, U.: Side: representation learning in signed directed networks. In: WWW (2018)
25.
Kim, Y., Son, S.W., Jeong, H.: Finding communities in directed networks. Phys. Rev. E 81(1), 016103 (2010)CrossRef
26.
27.
Kunegis, J., Lommatzsch, A.: Learning spectral graph transformations for link prediction. In: Proceedings of the 26th Annual International Conference on Machine Learning, ACM, pp. 561–568 (2009)
28.
Kunegis, J., Lommatzsch, A., Bauckhage, C.: The slashdot zoo: mining a social network with negative edges. In: Proceedings of the 18th International Conference on World Wide Web, ACM, pp. 741–750 (2009)
29.
Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., De Luca, E.W., Albayrak, S.: Spectral analysis of signed graphs for clustering, prediction and visualization. In: SDM. SIAM, vol. 10, pp. 559–559 (2010)
30.
Lee, J.R., Oveis Gharan, S., Trevisan, L.: Multi-way spectral partitioning and higher-order cheeger inequalities. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, ACM, pp. 1117–1130 (2012)
31.
Leicht, E.A., Newman, M.E.: Community structure in directed networks. Phys. Rev. Lett. 100(11), 118703 (2008)CrossRef
32.
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, pp. 1361–1370 (2010)
33.
Li, Y., Wu, X., Lu, A.: Analysis of spectral space properties of directed graphs using matrix perturbation theory with application in graph partition. In: 2015 IEEE International Conference on Data Mining (ICDM), IEEE, pp. 847–852 (2015)
34.
35.
Maaten, L.V.D., Hinton, G.: Visualizing data using T-SNE. J. Mach. Learn. Res. 9, 2579–2605 (2008)MATH
36.
Malliaros, F.D., Vazirgiannis, M.: Clustering and community detection in directed networks:a survey. Phys. Rep. 553, 95–142 (2013)MathSciNetCrossRefMATH
37.
Meila, M., Pentney, W.: Clustering by weighted cuts in directed graphs. SIAM DM PR127, 10 (2007)
38.
Mikolov, T., Corrado, G., Chen, K., Dean, J.: Efficient estimation of word representations in vector space. In: ICLR (2013)
39.
Mirzal, A., Furukawa, M.: Eigenvectors for clustering: unipartite, bipartite, and directed graph cases. Electron. Inf. Eng. 1, 303–309 (2010)
40.
Newman, M.E., Leicht, E.A.: Community structure in directed networks. PRL 100, 118703 (2007)
41.
Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech. 03, 3024 (2009)CrossRef
42.
Niepert, M., Ahmed, M., Kutzkov, K.: Learning convolutional neural networks for graphs. In: ICML (2016)
43.
Noutsos, D.: On Perron–Frobenius property of matrices having some negative entries. Linear Algebra Appl. 412, 132–153 (2006)MathSciNetCrossRefMATH
44.
Ou, M., Cui, P., Pei, J., Zhu, W.: Asymmetric transitivity preserving graph embedding. In: KDD (2016)
45.
Pan, S., Wu, J., Zhu, X., Zhang, C., Wang, Y.: Tri-party deep network representation. In: IJCAI (2016)
46.
Papadimitriou, C.H., Tamaki, H., Raghavan, P., Vempala, S.: Latent semantic indexing: a probabilistic analysis. In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM, pp. 159–168 (1998)
47.
48.
Prakash, B., Sridharan, A., Seshadri, M., Machiraju, S., Faloutsos, C.: EigenSpokes: surprising patterns and scalable community chipping in large graphs. In: Advances in Knowledge Discovery and Data Mining pp. 435–448 (2010)
49.
Sampson, S.F.: Crisis in a cloister. Ph.D. thesis, Cornell University, Ithaca (1969)
50.
Satuluri, V., Parthasarathy, S.: Symmetrizations for clustering directed graphs. In: EDBT, ACM, pp. 343–354 (2011)
51.
Seary, A., Richards, W.: Spectral methods for analyzing and visualizing networks: an introduction. National Research Council, Dynamic Social Network Modelling and Analysis: Workshop Summary and Papers, pp. 209–228 (2003)
52.
Stewart, G.W.: Error bounds for approximate invariant subspaces of closed linear operators. SIAM J. Numer. Anal. 8, 796–808 (1971)MathSciNetCrossRefMATH
53.
54.
Stewart, G.W., Sun, J.: Matrix Perturbation Theory. Academic Press, Cambridge (1990)MATH
55.
56.
57.
58.
Traag, V., Bruggeman, J.: Community detection in networks with positive and negative links. Phys. Rev. E 80, 036115 (2009)CrossRef
59.
Tu, C., Zhang, W., Liu, Z., Sun, M.: Max-margin deepwalk: discriminative learning of network representation. In: IJCAI (2016)
60.
Satuluri, V., Parthasarathy, S.: Symmetrizations for clustering directed graphs. In: EDBT pp. 343–354 (2011)
61.
62.
Wang, D., Cui, P., Zhu, W.: Structural deep network embedding. In: KDD (2016)
63.
Wang, S., Tang, J., Aggarwal, C., Chang, Y., Liu, H.: Signed network embedding in social media. In: Proceedings of the 2017 SIAM International Conference on Data Mining, SIAM, pp. 327–335 (2017)
64.
65.
Wu, L., Wu, X., Lu, A., Li, Y.: On spectral analysis of signed and dispute graphs. In: 2014 IEEE International Conference on Data Mining, ICDM 2014, Shenzhen, China, December 14–17, 2014, pp. 1049–1054 (2014)
66.
Wu, L., Wu, X., Lu, A., Li, Y.: On spectral analysis of signed and dispute graphs: application to community structure. IEEE Trans. Knowl. Data Eng. 29(7), 1480–1493 (2017)CrossRef
67.
Wu, L., Wu, X., Lu, A., Zhou, Z.: A spectral approach to detecting subtle anomalies in graphs. J. Intell. Inf. Syst. 41(2), 313–337 (2013)CrossRef
68.
Wu, L., Ying, X., Wu, X., Lu, A., Zhou, Z.H.: Spectral analysis of k-balanced signed graphs. PAKDD 2, 1–12 (2011)
69.
Wu, L., Ying, X., Wu, X., Zhou, Z.H.: Line orthogonality in adjacency eigenspace with application to community partition. In: IJCAI, pp. 2349–2354 (2011)
70.
Yang, C., Liu, Z., Zhao, D., Sun, M., Chang, E.Y.: Network representation learning with rich text information. In: IJCAI (2015)
71.
Yang, Z., Cohen, W.W., Salakhutdinov, R.: Revisiting semi-supervised learning with graph embeddings. In: ICML (2016)
72.
Ying, X., Wu, L., Wu, X.: A spectrum-based framework for quantifying randomness of social networks. IEEE Trans. Knowl. Data Eng. 23(12), 1842–1856 (2011)CrossRef
73.
Ying, X., Wu, X.: On randomness measures for social networks. In: SDM (2009)
74.
Ying, X., Wu, X., Barbará, D.: Spectrum based fraud detection in social networks. In: ICDE, pp. 912–923 (2011)
75.
Yuan, S., Wu, X., Li, J., Lu, A.: Spectrum-based deep neural networks for fraud detection. In: CIKM (2017)
76.
77.
Zaslavsky, B.G., Tam, B.S.: On the jordan form of an irreducible matrix with eventually nonnegative powers. Linear Algebra Appl. 302, 303–330 (1999)MathSciNetCrossRefMATH
78.
Zaslavsky, T.: Matrices in the theory of signed simple graphs. In: Proceedings of International Conference Discrete Mathematics, ICDM (2008)
79.
Zhou, D., Burges, C.J.C.: Spectral clustering and transductive learning with multiple views. In: ICML pp. 1159–1166 (2007)
80.
Zhou, D., Huang, J., Schölkopf, B.: Learning from labeled and unlabeled data on a directed graph. In: ICML, pp. 1036–1043. ACM (2005)
81.
Zhou, D., Schölkopf, B., Hofmann, T.: Semi-supervised learning on directed graphs. In: NIPS (2005)
Metadaten
Titel
On spectral analysis of directed signed graphs
verfasst von
Yuemeng Li
Shuhan Yuan
Xintao Wu
Aidong Lu
Publikationsdatum
20.06.2018
Verlag
Springer International Publishing
Erschienen in
International Journal of Data Science and Analytics / Ausgabe 2/2018
Print ISSN: 2364-415X
Elektronische ISSN: 2364-4168
DOI
https://doi.org/10.1007/s41060-018-0143-9