Graph Theoretic and Spectral Analysis of Enron Email Data

Analysis of social networks to identify communities and model their evolution has been an active area of recent research. This paper analyzes the Enron email data set to discover structures within the organization. The analysis is based on constructing an email graph and studying its properties with both graph theoretical and spectral analysis techniques. The graph theoretical analysis includes the computation of several graph metrics such as degree distribution, average distance ratio, clustering coefficient and compactness over the email graph. The spectral analysis shows that the email adjacency matrix has a rank-2 approximation. It is shown that preprocessing of data has significant impact on the results, thus a standard form is needed for establishing a benchmark data. Anurat Chapanond is currently a Ph.D. student in Computer Science, RPI. Anurat graduated B. Eng. degree in Computer Engineering from Chiangmai University (Thailand) in 1997, M. S. in Computer Science from Columbia University in 2002. His research interest is in web data mining analyses and algorithms. M.S. Krishnamoorthy received the B.E. degree (with honors) from Madras University in 1969, the M. Tech degree in Electrical Engineering from the Indian Institute of Technology, Kanpur, in 1971, and the Ph. D. degree in Computer Science, also from the Indian Institute of Technology, in 1976. From 1976 to 1979, he was an Assistant Professor of Computer Science at the Indian Institute of Technology, Kanpur. From 1979 to 1985, he was an Assistant Professor of Computer Science at Rensselaer Polytechnic Institute, Troy, NY, and since, 1985, he has been an Associate Professor of Computer Science at Rensselaer. Dr. Krishnamoorthy's research interests are in the design and analysis of combinatorial and algebraic algorithms, visualization algorithms and programming environments. Bulent Yener is an Associate Professor in the Department of Computer Science and Co-Director of Pervasive Computing and Networking Center at Rensselaer Polytechnic Institute in Troy, New York. He is also a member of Griffiss Institute of Information Assurance. Dr. Yener received MS. and Ph.D. degrees in Computer Science, both from Columbia University, in 1987 and 1994, respectively. Before joining to RPI, he was a Member of Technical Staff at the Bell Laboratories in Murray Hill, New Jersey. His current research interests include bioinformatics, medical informtatics, routing problems in wireless networks, security and information assurance, intelligence and security informatics. He has served on the Technical Program Committee of leading IEEE conferences and workshops. Currently He is an associate editor of ACM/Kluwer Winet journal and the IEEE Network Magazine. Dr. Yener is a Senior Member of the IEEE Computer Society.     

Scan Statistics on Enron Graphs

We introduce a theory of scan statistics on graphs and apply the ideas to the problem of anomaly detection in a time series of Enron email graphs. Previous presentation: Workshop on Link Analysis, Counterterrorism and Security at the SIAM International Conference on Data Mining, Newport Beach, CA, April 23, 2005. Carey E. Priebe received the B.S. degree in mathematics from Purdue University in 1984, the M.S. degree in computer science from San Diego State University in 1988, and the Ph.D. degree in information technology (computational statistics) from George Mason University in 1993. From 1985 to 1994 he worked as a mathematician and scientist in the US Navy research and development laboratory system. Since 1994 he has been a professor in the Department of Applied Mathematics and Statistics, Whiting School of Engineering, Johns Hopkins University, Baltimore, Maryland. At Johns Hopkins, he holds joint appointments in the Department of Computer Science and the Center for Imaging Science. He is a past President of the Interface Foundation of North America—Computing Science & Statistics, a past Chair of the Section on Statistical Computing of the American Statistical Association, and on the editorial boards of Journal of Computational and Graphical Statistics, Computational Statistics and Data Analysis, and Computational Statistics. His research interests are in computational statistics, kernel and mixture estimates, statistical pattern recognition, statistical image analysis, and statistical inference for high-dimensional and graph data. He was elected Fellow of the American Statistical Association in 2002. John M. Conroy received a B.S. in Mathematics from Saint Joseph's University in 1980 and a Ph.D. in Applied Mathematics from the University of Maryland in 1986. Since then he has been a research staff member for the IDA Center for Computing Sciences in Bowie, MD. His research interest is applications of numerical linear algebra. He is a member of the Society for Industrial and Applied Mathematics, Institute of Electrical and Electronics Engineers (IEEE), and the Association for Computational Linguistics. David J. Marchette received a B.A. in 1980, and an M.A. in mathematics in 1982, from the University of California at San Diego. He received a Ph.D. in Computational Sciences and Informatics in 1996 from George Mason University under the direction of Ed Wegman. From 1985–1994 he worked at the Naval Ocean Systems Center in San Diego doing research on pattern recognition and computational statistics. In 1994 he moved to the Naval Surface Warfare Center in Dahlgren Virginia where he does research in computational statistics and pattern recognition, primarily applied to image processing, text processing, automatic target recognition and computer security. Dr. Marchette is a Fellow of the American Statistical Society. Youngser Park received the B.E. degree in electrical engineering from Inha University in Korea in 1985, the M.S. degree in computer science from The George Washington University in 1991, and had pursued a doctoral degree there. From 1998 to 2000 he worked at the Johns Hopkins Medical Institutes as a senior research engineer. Since 2003 he is working as a research analyst in the Center for Imaging Science at the Johns Hopkins University. His research interests are clustering algorithm, pattern classification, and data mining.     

Structure in the Enron Email Dataset

We investigate the structures present in the Enron email dataset using singular value decomposition and semidiscrete decomposition. Using word frequency profiles, we show that messages fall into two distinct groups, whose extrema are characterized by short messages and rare words versus long messages and common words. It is surprising that length of message and word use pattern should be related in this way. We also investigate relationships among individuals based on their patterns of word use in email. We show that word use is correlated to function within the organization, as expected. Lastly, we show that relative changes to individuals' word usage over time can be used to identify key players in major company events. Presented at theWorkshop on Link Analysis, Counterterrorism and Security at the SIAM International Conference on Data Mining, 2005. P.S. Keila is a graduate student in the School of Computing at Queen's University. His research area is data mining in text. D.B. Skillicorn is a professor in the School of Computing at Queen's University, where he heads the Smart Information Management Laboratory. His research area is data mining using matrix decompositions, particularly applied to complex datasets in areas such as biomedicine, geochemistry, counterterrorism and fraud.     

The block decomposition of a vandermonde matrix and its applications

This paper presents a new algorithm for the solution of linear equations with a Vandermonde coefficient matrix. The algorithm can also be used to solve the dual problem. Since the algorithm uses a block decomposition of the matrix, it is especially suitable for parallel computation. A variation of the block decomposition leads to the efficient solution of the interpolation problem with complex-conjugate interpolation points where the coefficients of the interpolating polynomial are real. In addition the algorithm can be used to solve some kinds of confluent Vandermonde systems.W. P. Tang is a graduate student in the Computer Science Department at Stanford University, on leave from the Institute of Computing Technology of the Chinese Academy of Science in Peking.The work of Professor Golub was in part supported by NSF Grant No. MCS78-11985.     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

A normative framework for agent-based systems

One of the key issues in the computational representation of open societies relates to the introduction of norms that help to cope with the heterogeneity, the autonomy and the diversity of interests among their members. Research regarding this issue presents two omissions. One is the lack of a canonical model of norms that facilitates their implementation, and that allows us to describe the processes of reasoning about norms. The other refers to considering, in the model of normative multi-agent systems, the perspective of individual agents and what they might need to effectively reason about the society in which they participate. Both are the concerns of this paper, and the main objective is to present a formal normative framework for agent-based systems that facilitates their implementation. F. López y López is researcher of the Computer Science Faculty at the Benemérita Universidad Autónoma de Puebla in México, from where she got her first degree. She also gained a MSc in Computation from the Universidad Nacional Autónoma de México and a PhD in Computer Science from the University of Southampton in the United Kingdom. She is leading several theoretical and practical projects that use multi-agent systems as the main paradigm. Her research has been focused on Autonomous Normative Agents and Normative Multi-Agent Systems and she has published over 20 articles in these and related topics. M. Luck is Professor of Computer Science in the Intelligence, Agents, Multimedia Group of the School of Electronics and Computer Science at the University of Southampton, where he carries out research into the theory and practice of agent technology. He has published over 150 articles in these and related areas, both alone and in collaboration with others, and has published eight books. He is a member of the Executive Committee of AgentLink III, the European Network of Excellence for Agent-Based Computing. He is a co-founder of the European Multi-Agent Systems workshop series, is co-founder and Chair of the steering committee of the UK Multi-Agent Systems Workshops (UKMAS), and was a member of the Management Board of Agentcities.NET. Professor Luck is also a steering committee member for the Central and Eastern European Conference on Multi-Agent Systems. He is series editor for Artech House’s Agent Oriented Systems series, and an editorial board member of the Journal of Autonomous Agents and Multi-Agent Systems, the International Journal of Agent-Oriented Software Engineering, and ACM Transactions on Autonomous and Adaptive Systems. M. d’Inverno gained a BA in Mathematics and an MSc in Computation both from Oxford University. He also was awarded a PhD from University College London. He joined the University of Westminster in 1992 as a Lecturer, became a senior lecturer in 1998, a reader in 1999 and was appointed professor of computer science in 2001. He is interested in formal, principled approaches to modelling both natural and artificial systems in a computational setting. The main strand to this research, focuses on the application of formal methods in providing models of intelligent agent and multi-agent systems. His approach has sought to take a structured approach to the development of practical agent systems from theoretical models. He has published over 70 articles in these areas and has published four books and edited collections.     

Mapping deontic operators to abductive expectations

Deontic concepts and operators have been widely used in several fields where representation of norms is needed, including legal reasoning and normative multi-agent systems. The EU-funded SOCS project has provided a language to specify the agent interaction in open multi-agent systems. The language is equipped with a declarative semantics based on abductive logic programming, and an operational semantics consisting of a (sound and complete) abductive proof procedure. In the SOCS framework, the specification is used directly as a program for the verification procedure. In this paper, we propose a mapping of the usual deontic operators (obligations, prohibition, permission) to language entities, called expectations, available in the SOCS social framework. Although expectations and deontic operators can be quite different from a philosophical viewpoint, we support our mapping by showing a similarity between the abductive semantics for expectations and the Kripke semantics that can be given to deontic operators. The main purpose of this work is to make the computational machinery from the SOCS social framework available for the specification and verification of systems by means of deontic operators. Marco Alberti received his laurea degree in Electronic Engineering in 2001 and his Ph.D. in Information Engineering in 2005 from the University of Ferrara, Italy. His research interests include constraint logic programming and abductive logic programming, applied in particular to the specification and verification of multi-agent systems. He has been involved as a research assistants in national and European research projects. He currently has a post-doc position in the Department of Engineering at the University of Ferrara. Marco Gavanelli is currently assistant professor in the Department of Engineering at the University of Ferrara, Italy. He graduated in Computer Science Engineering in 1998 at the University of Bologna, Italy. He got his Ph.D. in 2002 at Ferrara University. His research interest include Artificial Intelligence, Constraint Logic Programming, Multi-criteria Optimisation, Abductive Logic Programming, Multi-Agent Systems. He is a member of ALP (the Association for Logic Programming) and AI*IA (the Italian Association for Artificial Intelligence). He has organised workshops, and is author of more than 30 publications between journals and conference proceedings. Evelina Lamma received her degree in Electronic Engineering from University of Bologna, Italy, in 1985 and her Ph.D. degree in Computer Science in 1990. Currently she is Full Professor at the Faculty of Engineering of the University of Ferrara where she teaches Artificial Intelligence and Foundations of Computer Science. Her research activity focuses around: – programming languages (logic languages, modular and object-oriented programming); – artificial intelligence; – knowledge representation; – intelligent agents and multi-agent systems; – machine learning. Her research has covered implementation, application and theoretical aspects. She took part to several national and international research projects. She was responsible of the research group at the Dipartimento di Ingegneria of the University of Ferrara in the UE ITS-2001-32530 Project (named SOCS), in the the context of the UE V Framework Programme - Global Computing Action. Paola Mello received her degree in Electronic Engineering from the University of Bologna, Italy, in 1982, and her Ph.D. degree in Computer Science in 1989. Since 1994 she has been Full Professor. She is enrolled, at present, at the Faculty of Engineering of the University of Bologna (Italy), where she teaches Artificial Intelligence. Her research activity focuses on programming languages, with particular reference to logic languages and their extensions, artificial intelligence, knowledge representation, expert systems with particular emphasis on medical applications, and multi-agent systems. Her research has covered implementation, application and theoretical aspects and is presented in several national and international publications. She took part to several national and international research projects in the context of computational logic. Giovanni Sartor is Marie-Curie professor of Legal informatics and Legal Theory at the European University Institute of Florence and professor of Computer and Law at the University of Bologna (on leave), after obtaining a PhD at the European University Institute (Florence), working at the Court of Justice of the European Union (Luxembourg), being a researcher at the Italian National Council of Research (ITTIG, Florence), and holding the chair in Jurisprudence at Queen’s University of Belfast (where he now is honorary professor). He is co-editor of the Artificial Intelligence and Law Journal and has published widely in legal philosophy, computational logic, legislation technique, and computer law. Paolo Torroni is Assistant Professor in computing at the Faculty of Engineering of the University of Bologna, Italy. He obtained a PhD in Computer Science and Electronic Engineering in 2002, with a dissertation on logic-based agent reasoning and interaction. His research interests mainly focus on computational logic and multi-agent systems research, including logic programming, abductive and hypothetical reasoning, agent interaction, dialogue, negotiation, and argumentation. He is in the steering committee of the CLIMA and DALT international workshops and of the Italian logic programming interest group GULP.     

Privacy Preserving Link Analysis on Dynamic Weighted Graph

Link analysis algorithms have been used successfully on hyperlinked data to identify authoritative documents and retrieve other information. They also showed great potential in many new areas such as counterterrorism and surveillance. Emergence of new applications and changes in existing ones created new opportunities, as well as difficulties, for them: (1) In many situations where link analysis is applicable, there may not be an explicit hyperlinked structure. (2) The system can be highly dynamic, resulting in constant update to the graph. It is often too expensive to rerun the algorithm for each update. (3) The application often relies heavily on client-side logging and the information encoded in the graph can be very personal and sensitive. In this case privacy becomes a major concern. Existing link analysis algorithms, and their traditional implementations, are not adequate in face of these new challenges. In this paper we propose the use of a weighted graph to define and/or augment a link structure. We present a generalized HITS algorithm that is suitable for running in a dynamic environment. The algorithm uses the idea of “lazy update” to amortize cost across multiple updates while still providing accurate ranking to users in the mean time. We prove the convergence of the new algorithm and evaluate its benefit using the Enron email dataset. Finally we devise a distributed implementation of the algorithm that preserves user privacy thus making it socially acceptable in real-world applications. This material is based upon work supported by the National Science Foundation under Grant No. 0222745. Part of this work was presented at the SDM05 Workshop on Link Analysis in Newport Beach, California, April 2005. Yitao Duan is a Ph.D. candidate in Computer Science at the University of California, Berkeley. His research interests include practical privacy enhancing technologies for a variety of situations including: ubiquitous computing, collaborative work, smart spaces, and location-aware services etc. His research goal is to develop provably strong (cryptographic and information-theoretic) protocols that are practically realizable. He received his B.S. and M.S. in Mechanical Engineering from Beijing University of Aeronautics and Astronautics, China in 1994 and 1997. Jingtao Wang is a Ph.D. student in Computer Science at the University of California, Berkeley. His research interests include context-aware computing, novel end-user interaction techniques and statistical machine learning. He was a research member, later a staff research member and team lead at IBM China Research Lab from 1999 to 2002, working on online handwriting recognition technologies for Asian languages. He received his B.E. and M.E. in electrical and computer engineering from Xi'an Jiaotong University, China in 1996 and 1999. He is a member of the ACM and ACM SIGCHI since 2000. Matthew Kam is a Ph.D. student in computer science at the University of California, Berkeley working on educational technology and human-computer interaction for low-income communities in developing regions. He received a B.A. in economics and a B.S. in Electrical Engineering and Computer Sciences, also from Berkeley. He is a member of the ACM and Engineers for a Sustainable World. John Canny is the Paul and Stacy Jacobs Distinguished Professor of Engineering in Computer Science at the University of California, Berkeley. His research is in human-computer interaction, with an emphasis on modeling methods and privacy approaches using cryptography. He received his Ph.D. in 1987 at the MIT AI Lab. His dissertation on Robot Motion Planning received the ACM dissertation award. He received a Packard Foundation Faculty Fellowship and a Presidential Young Investigator Award. His peer-reviewed publications span robotics, computational geometry, physical simulation, computational algebra, theory and algorithms, information retrieval, HCI and CSCW and cryptography.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.     

Validation and verification of social processes within agent-based computational organization models

The use of simulation modeling in computational analysis of organizations is becoming a prominent approach in social science research. However, relying on simulations to gain intuition about social phenomena has significant implications. While simulations may give rise to interesting macro-level phenomena, and sometimes even mimic empirical data, the underlying micro and macro level processes may be far from realistic. Yet, this realism may be important to infer results that are relevant to existing theories of social systems and to policy making. Therefore, it is important to assess not only predictive capability but also explanation accuracy of formal models in terms of the degree of realism reflected by the embedded processes. This paper presents a process-centric perspective for the validation and verification (V&V) of agent-based computational organization models. Following an overview of the role of V&V within the life cycle of a simulation study, emergent issues in agent-based organization model V&V are outlined. The notion of social contract that facilitates capturing micro level processes among agents is introduced to enable reasoning about the integrity and consistency of agent-based organization designs. Social contracts are shown to enable modular compositional verification of interaction dynamics among peer agents. Two types of consistency are introduced: horizontal and vertical consistency. It is argued that such local consistency analysis is necessary, but insufficient to validate emergent macro processes within multi-agent organizations. As such, new formal validation metrics are introduced to substantiate the operational validity of emergent macro-level behavior. Levent Yilmaz is Assistant Professor of Computer Science and Engineering in the College of Engineering at Auburn University and co-founder of the Auburn Modeling and Simulation Laboratory of the M&SNet. Dr. Yilmaz received his Ph.D. and M.S. degrees from Virginia Polytechnic Institute and State University (Virginia Tech). His research interests are on advancing the theory and methodology of simulation modeling, agent-directed simulation (to explore dynamics of socio-technical systems, organizations, and human/team behavior), and education in simulation modeling. Dr. Yilmaz is a member of ACM, IEEE Computer Society, Society for Computer Simulation International, and Upsilon Pi Epsilon. URL: http://www.eng.auburn.edu/~yilmaz     

On the invariance of perturbed null vectors under column scaling

Summary It is shown that the approximate null vector of a perturbed degenerate matrix behaves linearly under column scaling up to second order terms in the perturbation. This result has important consequences for an estimation technique known to numerical analysts as total least squares and to statisticians as latent root regression.Dedicated to F.L. Bauer on the occasion of his 60th birthdayDepartment of Computer Science and Institute for Physical Science and Technology, University of Maryland at College Park. This work was done while the author was at the Scientific Computing Division of the National Bureau of Standards     

Complete harmonic stable minimal hypersurfaces in a Riemannian manifold

In this paper, we will introduce the notion of harmonic stability for complete minimal hypersurfaces in a complete Riemannian manifold. The first result we prove, is that a complete harmonic stable minimal surface in a Riemannian manifold with non-negative Ricci curvature is conformally equivalent to either a plane R ² or a cylinder R × S ¹, which generalizes a theorem due to Fischer-Colbrie and Schoen [12]. The second one is that an n ≥ 2-dimensional, complete harmonic stable minimal, hypersurface M in a complete Riemannian manifold with non-negative sectional curvature has only one end if M is non-parabolic. The third one, which we prove, is that there exist no non-trivial L ²-harmonic one forms on a complete harmonic stable minimal hypersurface in a complete Riemannian manifold with non-negative sectional curvature. Since the harmonic stability is weaker than stability, we obtain a generalization of a theorem due to Miyaoka [20] and Palmer [21]. Research partially Supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology, Japan. The author’s research was supported by grant Proj. No. KRF-2007-313-C00058 from Korea Research Foundation, Korea. Authors’ addresses: Qing-Ming Cheng, Department of Mathematics, Faculty of Science and Engineering, Saga University, Saga 840-8502, Japan; Young Jin Suh, Department of Mathematics, Kyungpook National University, Taegu 702-701, South Korea     

Asymptotic Expansions for the Coefficients of eP(z)

If P is a real polynomial with non-negative coefficients, thenone can obtain a complete asymptotic expansion for the nth coefficientof e^P(z). The proof requires the following result: the coefficientsin the Stirling expansion for the gamma function are all differentfrom zero. Department of Mathematics and Computer Science Drexel UniversityPhiladelphia PA 19104, USA     

A cognitively based simulation of academic science

The models used in social simulation to date have mostly been very simplistic cognitively, with little attention paid to the details of individual cognition. This work proposes a more cognitively realistic approach to social simulation. It begins with a model created by Gilbert (1997) for capturing the growth of academic science. Gilbert’s model, which was equation-based, is replaced here by an agent-based model, with the cognitive architecture CLARION providing greater cognitive realism. Using this cognitive agent model, results comparable to previous simulations and to human data are obtained. It is found that while different cognitive settings may affect the aggregate number of scientific articles produced, they do not generally lead to different distributions of number of articles per author. The paper concludes with a discussion of the correspondence between the model and the constructivist view of academic science. It is argued that using more cognitively realistic models in simulations may lead to novel insights. Isaac Naveh obtained a master’s degree in computer science at the University of Missouri. His research interests include hybrid cognitive models and multi-agent learning. Ron Sun is Professor of Cognitive Science at Rensselaer Polytechnic Institute, and formerly the James C. Dowell Professor of Engineering and Professor of Computer Science at University of Missouri-Columbia. He received his Ph.D in 1992 from Brandeis University. His research interest centers around studies of cognition, especially in the areas of cognitive architectures, human reasoning and learning, cognitive social simulation, and hybrid connectionist models. For his paper on integrating rule-based and connectionist models for accounting for human everyday reasoning, he received the 1991 David Marr Award from Cognitive Science Society. He is the founding co-editor-in-chief of the journal Cognitive Systems Research, and also serves on the editorial boards of many other journals. He is the general chair and program chair for CogSci 2006, and a member of the Governing Board of International Neural Networks Society. His URL is: http://www.cogsci.rpi.edu/~rsun     

A stochastic programming model for funding single premium deferred annuities

Single Premium Deferred Annuities (SPDAs) are investment vehicles, offered to investors by insurance companies as a means of providing income past their retirement age. They are mirror images of insurance policies. However, the propensity of individuals to shift part, or all, of their investment into different annuities creates substantial uncertainties for the insurance company. In this paper we develop amultiperiod, dynamic stochastic program that deals with the problem of funding SPDA liabilities. The model recognizes explicitly the uncertainties inherent in this problem due to both interest rate volatility and the behavior of individual investors. Empirical results are presented with the use of the model for the funding of an SPDA liability stream using government bonds, mortgage-backed securities and derivative products. Research partially supported by NSF grants CCR-9104042 and SES-91-00216, and AFOSR grant 91-0168. Computing resources were made available by AHPCRC at the University of Minnesota, by NPAC at Syracuse University, New York, and by the GRASP Laboratory at Computer Science Department at University of Pennsylvania.     

Communication Networks from the Enron Email Corpus “It's Always About the People. Enron is no Different”

The Enron email corpus is appealing to researchers because it represents a rich temporal record of internal communication within a large, real-world organization facing a severe and survival-threatening crisis. We describe how we enhanced the original corpus database and present findings from our investigation undertaken with a social network analytic perspective. We explore the dynamics of the structure and properties of the organizational communication network, as well as the characteristics and patterns of communicative behavior of the employees from different organizational levels. We found that during the crisis period, communication among employees became more diverse with respect to established contacts and formal roles. Also during the crisis period, previously disconnected employees began to engage in mutual communication, so that interpersonal communication was intensified and spread through the network, bypassing formal chains of communication. The findings of this study provide valuable insight into a real-world organizational crisis, which may be further used for validating or developing theories and dynamic models of organizational crises; thereby leading to a better understanding of the underlying causes of, and response to, organization failure. Jana Diesner is a Research Associate and Linguistic Programmer at the Center for Computational Analysis of Social and Organizational Systems at the School of Computer Science (CASOS), Carnegie Mellon University (CMU). She received her Masters in Communications from Dresden University of Technology in 2003. She had been a research scholar at the Institute for Complex Engineered System at CMU in 2001 and 2002. Her research combines computational linguistics, social network analysis and computational organization theory. Terrill L. Frantz is a post-doc researcher at the Center for Computational Analysis of Social and Organizational Systems (CASOS) in the School of Computer Science at Carnegie Mellon University. His research involves studying the dynamics of organization social-networks and behavior via computer modeling and simulation. He is developing an expertise in workforce integration strategy and policy evaluation during organization mergers. He earned his doctorate (Ed.D. in Organization Change) from Pepperdine University, a MBA from New York University and a BS in Business Administration (Computer Systems Management) from Drexel University. Prior to entering academic research, for nearly 20 years he was a software applications development manager in the global financial services and industrial chemicals industries; most recently as a Vice President in Information Technology at Morgan Stanley in Hong Kong, New York and London. Kathleen M. Carley is a professor at the Institute for Software Research International in the School of Computer Science at Carnegie Mellon University. She is the director of the center for Computational Analysis of Social and Organizational Systems (CASOS) <http://www.casos.cs.cmu.edu/>, a university wide interdisciplinary center that brings together network analysis, computer science and organization science (www.casos.ece.cmu.edu) and has an associated NSF funded training program for Ph.D. students. She carries out research that combines cognitive science, social networks and computer science to address complex social and organizational problems. Her specific research areas are computational social and organization theory, group, organizational and social adaptation and evolution, social and dynamic network analysis, computational text analysis, and the impact of telecommunication technologies and policy on communication, information diffusion, disease contagion and response within and among groups particularly in disaster or crisis situations.     

A convergence theorem of Rosen’s gradient projection method

Since Rosen’s gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence theorem is given in this paper. Part of this author’s work was done while he studied at the Department of Mathematics, University of California at Santa Barbara, and was supported by the National Science Foundation under Grant No. MCS83-14977. Part of this author’s work was done while he visited the Computer Science Department, University of Minnesota, Minneapolis, and was supported by the National Science Foundation under Grant No. MCS81-01214.     

Fast matrix multiplication is stable

We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of Bini and Lotti [Numer. Math. 36:63–72, 1980]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in Cohn and Umans [Foundations of Computer Science, 44th Annual IEEE Symposium, pp. 438–449, 2003] and Cohn et al. [Foundations of Computer Science, 46th Annual IEEE Symposium, pp. 379–388, 2005] are all included in the class of algorithms to which our analysis applies, and are therefore numerically stable. We perform detailed error analysis for three specific fast group-theoretic algorithms. J. Demmel acknowledges support of NSF under grants CCF-0444486, ACI-00090127, CNS-0325873 and of DOE under grant DE-FC02-01ER25478. I. Dumitriu acknowledges support of the Miller Institute for Basic Research in Science. R. Kleinberg is supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.