Automated social hierarchy detection through email network analysis

ABSTRACT

This paper provides a novel algorithm for automatically extracting social hierarchy data from electronic communication behavior. The algorithm is based on data mining user behaviors to automatically analyze and catalog patterns of communications between entities in a email collection to extract social standing. The advantage to such automatic methods is that they extract relevancy between hierarchy levels and are dynamic over time.

We illustrate the algorithms over real world data using the Enron corporation's email archive. The results show great promise when compared to the corporations work chart and judicial proceeding analyzing the major players.

REFERENCES

• 1: Ziv Bar-Yossef , Ido Guy , Ronny Lempel , Yoelle S. Maarek , Vladimir Soroka, Cluster Ranking with an Application to Mining Mailbox Networks, Proceedings of the Sixth International Conference on Data Mining, p.63-74, December 18-22, 2006 [doi>10.1109/ICDM.2006.35]
• 2: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 3: Giuseppe Carenini , Raymond T. Ng , Xiaodong Zhou, Scalable discovery of hidden emails from large folders, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081934]
• 4: W. Cohen. Enron data set, March 2004.
• 5: D. G. Deepak P and V. Varshney. Analysis of enron email threads and quantification of employee responsiveness. In Proceedings of the Text Mining and Link Analysis Workshop on International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007.
• 6: J. Diesner and K. Carley. Exploration of communication networks from the enron email corpus. In Proceedings of Workshop on Link Analysis, Counterterrorism and Security, Newport Beach CA, 2005.
• 7: Jana Diesner , Terrill L. Frantz , Kathleen M. Carley, Communication Networks from the Enron Email Corpus "It's Always About the People. Enron is no Different", Computational & Mathematical Organization Theory, v.11 n.3, p.201-228, October 2005 [doi>10.1007/s10588-005-5377-0]
• 8: T. Elsayed and D. W. Oard. Modeling identity in archival collections of email: a preliminary study. In Third Conference on Email and Anti-spam (CEAS), Mountain View, CA, July 2006.
• 9: Tom Fawcett , Foster Provost, Activity monitoring: noticing interesting changes in behavior, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.53-62, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312195]
• 10: L. Freeman. Centrality in networks: I. conceptual clarification. Social networks, 1:215-239, 1979.
• 11: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 12: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 13: H. G. Goldberg, J. D. Kirkland, D. Lee, P. Shyr, and D. Thakker. The NASD securities observation, news analysis and regulation system (sonar). In IAAI 2003, 2003.
• 14: Shlomo Hershkop , Salvatore J. Stolfo, Behavior-based email analysis with application to spam detection, Columbia University, New York, NY, 2006
• 15: D. F. Joshua O'Madadhain and S. White. Java universal network/graph framework, 2006. JUNG 1.7.4.
• 16: P. S. Keila , D. B. Skillicorn, Structure in the Enron Email Dataset, Computational & Mathematical Organization Theory, v.11 n.3, p.183-199, October 2005 [doi>10.1007/s10588-005-5379-y]
• 17: J. D. Kirkland, T. E. Senator, J. J. Hayden, T. Dybala, H. G.Goldberg, and P. Shyr. The nasd regulation advanced detection system (ads). AI Magazine, 20(1):55-67, 1999.
• 18: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 19: B. Klimt and Y. Yang. The enron corpus: A new dataset for email classification research. In European Conference on Machine Learning, Pisa, Italy, 2004.
• 20: B. Klimt and Y. Yang. Introducing the enron corpus. In First Conference on Email and Anti-spam (CEAS), Mountain View, CA, 2004.
• 21: B. Klimt and Y. Yang. Introducing the enron corpus. In CEAS, 2004.
• 22: Stuart Madnick , Richard Wang , Xiang Xian, The Design and Implementation of a Corporate Householding Knowledge Processor to Improve Data Quality, Journal of Management Information Systems, v.20 n.3, p.41-70, Number 3/Winter 2003
• 23: S. Madnick, R. Wang, and W. Zhang. A framework for corporate householding. In C. Fisher and B. Davidson, editors, Proceedings of the Seventh International Conference on Information Quality, pages 36-40, Cambridge, MA, November 2002.
• 24: A. McCallum, A. Corrada-Emmanuel, and X. Wang. The author-recipient-topic model for topic and role discovery in social networks: Experiments with enron and academic email. In NIPS'04 Workshop on 'Structured Data and Representations in Probabilistic Models for Categorization', Whistler, B.C., 2004.
• 25: C. Perlich and Z. Huang. Relational learning for customer relationship management. In Proceedings of International Workshop on Customer Relationship Management: Data Mining Meets Marketing, 2005.
• 26: Claudia Perlich , Foster Provost, Distribution-based aggregation for relational learning with identifier attributes, Machine Learning, v.62 n.1-2, p.65-105, February 2006 [doi>10.1007/s10994-006-6064-1]
• 27: Ted E. Senator, Link mining applications: progress and challenges, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.76-83, December 2005 [doi>10.1145/1117454.1117465]
• 28: J. Shetty and J. Adibi. The enron email dataset database schema and brief statistical report, 2004.
• 29: Jitesh Shetty , Jafar Adibi, Discovering important nodes through graph entropy the case of Enron email database, Proceedings of the 3rd international workshop on Link discovery, p.74-81, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134282]
• 30: M. Sparrow. The application of network analysis to criminal intelligence: an assessment of the prospects. Social networks, 13:251-274, 1991.
• 31: Salvatore J. Stolfo , Germán Creamer , Shlomo Hershkop, A temporal based forensic analysis of electronic communication, Proceedings of the 2006 international conference on Digital government research, May 21-24, 2006, San Diego, California [doi>10.1145/1146598.1146609]
• 32: Salvatore J. Stolfo , Shlomo Hershkop , Chia-Wei Hu , Wei-Jen Li , Olivier Nimeskern , Ke Wang, Behavior-based modeling and its application to Email analysis, ACM Transactions on Internet Technology (TOIT), v.6 n.2, p.187-221, May 2006 [doi>10.1145/1149121.1149125]
• 33: B. Taskar, E. Segal, and D. Koller. Probabilistic classification and clustering in relational data. In B. Nebel, editor, Proceeding of IJCAI-01, 17th International Joint Conference on Artificial Intelligence, pages 870-878, Seattle, US, 2001.
• 34: B. Taskar, M. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. In Proceedings of Neural Information Processing Systems, 2004., 2004.

INDEX TERMS

Keywords:
Enron, behavior profile, data, link mining, mining, social network