Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Centrality informed embedding of networks for temporal feature extraction

  • Original Article
  • Published:
Social Network Analysis and Mining Aims and scope Submit manuscript

Abstract

We propose a two-step methodology for exploring the temporal characteristics of a network. First, we construct a graph time series, where each snapshot is the result of a temporal whole-graph embedding. The embedding is carried out using the degree, Katz and betweenness centralities to characterize first and higher order proximities among vertices. Then a principal component analysis is performed over the collected temporal graph samples, which exhibits eigengraphs, graphs whose temporal weight variations model the sampled graph series. Analysis of the temporal timeline of each of the main eigengraphs reveals moments of importance in terms of structural graph changes. Parameters such as the dimension of the embeddings and the number of temporal samples are explored. Two case studies are presented: a Bitcoin subgraph, where findings are cross-checked by looking at the subgraph behavior itself, and the Enron email network, which allows us to compare our findings with prior studies. In both cases, the proposed methodology successfully identified temporal structural changes in the graph evolution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Akcora C, Kantarcioglu M, Gel Y (2018) Blockchain data analytics. In: IEEE International Conference on Data Mining (ICDM)

  • Batagelj V, Praprotnik S (2016) An algebraic approach to temporal network analysis based on temporal quantities. Soc Netw Anal Min 6(28):1–22

    MATH  Google Scholar 

  • Bourgain J (1985) On Lipschitz embedding of finite metric spaces in Hilbert space. Isr J Math 52(1–2):46–52

    Article  MathSciNet  Google Scholar 

  • Cai H, Zheng VW, Chang KC-C (2018) A comprehensive survey of graph embedding: problems, techniques and applications. IEEE Trans Knowl Data Eng 30:1616–1637

    Article  Google Scholar 

  • Estrada E (2011) The structure of complex networks: theory and applications. Oxford University Press Inc., Oxford

    Book  Google Scholar 

  • Fraiman D, Fraiman N, Fraiman R (2017) Nonparametric statistics of dynamic networks with distinguishable nodes. Test 26(3):546–573

    Article  MathSciNet  Google Scholar 

  • Goyal P, Ferrara E (2018) Graph embedding techniques, applications, and performance: a survey. Knowl-Based Syst 151:78–94

    Article  Google Scholar 

  • Goyal P, Kamra N, He X, Liu Y (2018) Dyngem: deep embedding method for dynamic graphs. arXiv preprint arXiv:1805.11273

  • Harrigan M, Fretter C (2016) The unreasonable effectiveness of address clustering. Tech. Rep. arXiv:1605.06369, arXiv

  • Holme P, Saramäki J (eds) (2013) Temporal networks. Springer, Berlin

    Google Scholar 

  • Klimt B, Yang Y (2004) The enron corpus: a new dataset for email classification research. In: European Conference on Machine Learning

  • Kondor D, Csabai I, Szüle J, Pósfai M, Vattay G (2014) Inferring the interplay between network structure and market effects in bitcoin. New J Phys 16:125003

    Article  Google Scholar 

  • Narayanan A, Chandramohan M, Venkatesan R, Chen L, Liu Y, Jaiswal S (2017) graph2vec: learning distributed representations of graphs. Workshop on mining and learning with graphs

  • Park Y, Priebe CE, Youssef A (2013) Anomaly detection in time series of graphs using fusion of graph invariants. IEEE J Sel Top Signal Process 7(1):67–75

    Article  Google Scholar 

  • Peel L, Clauset A (2015) Detecting change points in the large-scale structure of evolving networks. In: Proceedings of the twenty-ninth AAAI conference on artifical intelligence

  • Sarkar S, Guo R, Shakarian P (2019) Using network motifs to characterize temporal network evolution leading to diffusion inhibition. Soc Netw Anal Min 9(1):14

    Article  Google Scholar 

  • Sirovich L, Kirby M (1987) Low-dimensional procedure for the characterization of human faces. J Opt Soc Am A 4(3):519–524

    Article  Google Scholar 

  • Ye C, Wilson RC, Hancock ER (2018) Network analysis using entropy component analysis. J Complex Netw 6(3):404–429

    Article  MathSciNet  Google Scholar 

  • Zhu L, Guo D, Yin J, Ver Steeg G, Galstyan A (2016) Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Trans Knowl Data Eng 28(10):2765–2777

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Anwitaman Datta.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Enron scandal—chronology of events

Appendix: Enron scandal—chronology of events

Timeline

Event (non-exhaustive) summary

1999

 

November

Launch of EnronOnline, a global commodity trading web site

2000

 

January

Launch of Enron Broadband Service (EBS)

19 July

Announcement of EBS joining forces with Blockbuster

23 August

Enron stock reached all time high price of $90.75

3 October

Enron attorney discussed Timothy Belden’s strategies

1 November

FERC investigation exonerated Enron

December

At end of 2000, Enron declared $53 million earnings for Broadband

13 December

Announcement that Jeffrey Skilling would take over as CEO

2001

 

17 January

Rolling blackouts in California

1 February\(^\dagger \)

State lawmakers legislate to spend up to $10 billion for power

12 February\(^\dagger \)

Skilling was named CEO of Enron, replacing Lay

23 March

Enron conference call with analysts to boost stock

17 April

The ‘asshole” call: Jeffrey Skilling response to an analyst query

15 May\(^\dagger \)

California energy regulators adopted the highest rate increase in the state’s history

17 May\(^\dagger \)

California energy regulators uncovered evidence that some electrical power companies repeatedly shut down generating plants for unnecessary maintenance

26 May

Schwarzenegger, Lay, Milken meeting

5 June\(^\dagger \)

Karl Rove divested his stocks in energy, defense and pharmaceutical companies (including Enron)

11/12 July

Quarterly conference call

24-25 July

Skilling met analysts and investors in NY

14 August\(^\dagger \)

Skilling resigned; Lay named CEO again

22 August

Sherron Watkins met Lay to discuss accounting irregularities

16 October\(^\dagger \)

Enron announces $638 million in third-quarter losses

19 October\(^\dagger \)

Securities and Exchange Commission launches inquiry

23 October\(^\dagger \)

Lay professes confidence in Fastow to analysts

24 October\(^\dagger \)

Fastow ousted

9 November

Dynegy Inc. announced an agreement to buy Enron

19 November

Enron restated its 3rd-quarter earnings disclosing $690M debt

28 November

Dynegy called off its $8.4B merger with Enron

 

Enron stock plunged below $1

2 December

Enron Corp. under CEO Kenneth Lay filed for bankruptcy

2002

 

29 January

Stephen Cooper took over as interim Enron CEO

5 February

Lay cancelled senate committee appearance invoking the 5th

 

Fastow, Kopper, Lay invoked the 5th

7 February

Skilling testified

 

Fastow and Kopper invoked the 5th

14 February

Sharon Watkins testified

14 March

Former Enron auditor Arthur Andersen LLP indicted

  1. \(^\dagger \)Events not considered in Peel and Clauset (2015)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Oggier, F., Datta, A. Centrality informed embedding of networks for temporal feature extraction. Soc. Netw. Anal. Min. 11, 12 (2021). https://doi.org/10.1007/s13278-021-00720-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13278-021-00720-8

Keywords

Navigation