Email Surveillance Using Non-negative Matrix Factorization

In this study, we apply a non-negative matrix factorization approach for the extraction and detection of concepts or topics from electronic mail messages. For the publicly released Enron electronic mail collection, we encode sparse term-by-message matrices and use a low rank non-negative matrix factorization algorithm to preserve natural data non-negativity and avoid subtractive basis vector and encoding interactions present in techniques such as principal component analysis. Results in topic detection and message clustering are discussed in the context of published Enron business practices and activities, and benchmarks addressing the computational complexity of our approach are provided. The resulting basis vectors and matrix projections of this approach can be used to identify and monitor underlying semantic features (topics) and message clusters in a general or high-level way without the need to read individual electronic mail messages. Michael W. Berry is a Professor and Interim Department Head in the Department of Computer Science at the University of Tennessee and a faculty member in the Graduate School in Genome Science and Technology Program at the University of Tennessee and Oak Ridge National Laboratory. His research interests include information retrieval, data mining, scientific computing, computational science, and numerical linear algebra. He is a member of the Society for Industrial and Applied Mathematics (SIAM), Association for Computing Machinery (ACM), and the Computer Society of the Institute of Electrical and Electronics (IEEE). Professor Berry is on the editorial boards of “Computing in Science and Engineering” (IEEE Computer Society and the American Institute of Physics) and the SIAM Journal of Scientific Computing. Murray Browne is a Research Associate in the Department of Computer Science at the University of Tennessee. He is a member of the American Society for Information Science and Technology and has published numerous essays, book reviews, newspaper articles, and feature stories.     

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.     

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.     

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.     

Social Network Discovery by Mining Spatio-Temporal Events

Knowing patterns of relationship in a social network is very useful for law enforcement agencies to investigate collaborations among criminals, for businesses to exploit relationships to sell products, or for individuals who wish to network with others. After all, it is not just what you know, but also whom you know, that matters. However, finding out who is related to whom on a large scale is a complex problem. Asking every single individual would be impractical, given the huge number of individuals and the changing dynamics of relationships. Recent advancement in technology has allowed more data about activities of individuals to be collected. Such data may be mined to reveal associations between these individuals. Specifically, we focus on data having space and time elements, such as logs of people's movement over various locations or of their Internet activities at various cyber locations. Reasoning that individuals who are frequently found together are likely to be associated with each other, we mine from the data instances where several actors co-occur in space and time, presumably due to an underlying interaction. We call these spatio-temporal co-occurrences events, which we use to establish relationships between pairs of individuals. In this paper, we propose a model for constructing a social network from events, and provide an algorithm that mines these events from the data. Experiments on a real-life data tracking people's accesses to cyber locations have also yielded encouraging results. Hady W. Lauw is a graduate student at the School of Computer Engineering, Nanyang Technological University, Singapore. His research interests include spatio-temporal data mining, social network discovery, and link analyisis. He has a BEng in computer engineering from Nanyang Technological University. Ee-Peng Lim is an Associate Professor with the School of Computer Engineering, Nanyang Technological University, Singapore. He received his PhD from the University of Minnesota, Minneapolis in 1994 and B.Sc. in Computer Science from National University of Singapore. Ee-Peng's research interests include information integration, data/text/web mining, digital libraries, and wireless intelligence. He is currently an Associate Editor of the ACM Transactions on Information Systems (TOIS), International Journal of Digital Libraries (IJDL) and International Journal of Data Warehousing and Mining (IJDWM). He was the Program Co-Chair of the ACM/IEEE Joint Conference on Digital Libraries (JCDL 2004), and Conference/Program Co-Chairs of International Conference on Asian Digital Libraries (ICADL 2004). He has also served in the program committee of numerous international conferences. Dr Lim is a Senior Member of IEEE and a Member of ACM. HweeHwa Pang received the B.Sc.—with first class honors—and M.S. degrees from the National University of Singapore in 1989 and 1991, respectively, and the PhD degree from the University of Wisconsin at Madison in 1994, all in Computer Science. He is currently an Associate Professor at the Singapore Management University. His research interests include database management systems, data security and quality, operating systems, and multimedia servers. He has many years of hands-on experience in system implementation and project management. He has also participated in transferring some of his research results to industry. Teck-Tim Tan is an IT Manager (Operations) at the Centre for IT Services, Nanyang Technological University (NTU), Singapore. He administers and oversees NTU's campus-wide wireless LAN infrastructure which facilitates access to the University's vast IT resources and services practically anywhere on campus.     

A Network Analysis Model for Disambiguation of Names in Lists

In research and application, social networks are increasingly extracted from relationships inferred by name collocations in text-based documents. Despite the fact that names represent real entities, names are not unique identifiers and it is often unclear when two name observations correspond to the same underlying entity. One confounder stems from ambiguity, in which the same name correctly references multiple entities. Prior name disambiguation methods measured similarity between two names as a function of their respective documents. In this paper, we propose an alternative similarity metric based on the probability of walking from one ambiguous name to another in a random walk of the social network constructed from all documents. We experimentally validate our model on actor-actor relationships derived from the Internet Movie Database. Using a global similarity threshold, we demonstrate random walks achieve a significant increase in disambiguation capability in comparison to prior models. Bradley A. Malin is a Ph.D. candidate in the School of Computer Science at Carnegie Mellon University. He is an NSF IGERT fellow in the Center for Computational Analysis of Social and Organizational Systems (CASOS) and a researcher at the Laboratory for International Data Privacy. His research is interdisciplinary and combines aspects of bioinformatics, data forensics, data privacy and security, entity resolution, and public policy. He has developed learning algorithms for surveillance in distributed systems and designed formal models for the evaluation and the improvement of privacy enhancing technologies in real world environments, including healthcare and the Internet. His research on privacy in genomic databases has received several awards from the American Medical Informatics Association and has been cited in congressional briefings on health data privacy. He currently serves as managing editor of the Journal of Privacy Technology. Edoardo M. Airoldi is a Ph.D. student in the School of Computer Science at Carnegie Mellon University. Currently, he is a researcher in the CASOS group and at the Center for Automated Learning and Discovery. His methodology is based on probability theory, approximation theorems, discrete mathematics and their geometries. His research interests include data mining and machine learning techniques for temporal and relational data, data linkage and data privacy, with important applications to dynamic networks, biological sequences and large collections of texts. His research on dynamic network tomography is the state-of-the-art for recovering information about who is communicating to whom in a network, and was awarded honors from the ACM SIG-KDD community. Several companies focusing on information extraction have adopted his methodology for text analysis. He is currently investigating practical and theoretical aspects of hierarchical mixture models for temporal and relational data, and an abstract theory of data linkage. Kathleen M. Carley is a Professor of Computer Science in ISRI, School of Computer Science at Carnegie Mellon University. She received her Ph.D. from Harvard in Sociology. Her research combines cognitive science, social and dynamic networks, and computer science (particularly artificial intelligence and machine learning techniques) to address complex social and organizational problems. Her specific research areas are computational social and organization science, social adaptation and evolution, social and dynamic network analysis, and computational text analysis. Her models meld multi-agent technology with network dynamics and empirical data. Three of the large-scale tools she and the CASOS group have developed are: BioWar a city, scale model of weaponized biological attacks and response; Construct a models of the co-evolution of social and knowledge networks; and ORA a statistical toolkit for dynamic social Network data.     

Can tools help unify organization theory? Perspectives on the state of computational modeling

Scholars engaged in the study of work group and organizational behavior are increasingly calling for the use of integrated methods in conducting research, including the wider adoption of computational models for generating and testing new theory. Our review of the state of modern computational modeling incorporating social structures reveals steady increases in the incorporation of dynamic, adaptive, and realistic behaviors of agents in network settings, yet exposes gaps that must be addressed in the next generation of organizational simulation systems. We compare 28 models according to more than two hundred evaluation criteria, ranging from simple representations of agent demographic and performance characteristics, to more richly defined instantiations of behavioral attributes, interaction with non-agent entities, model flexibility, communication channels, simulation types, knowledge, transactive memory, task complexity, and resource networks. Our survey assesses trends across the wide set of criteria, discusses practical applications, and proposes an agenda for future research and development. Michael J. Ashworth is a doctoral candidate in computational organization science at Carnegie Mellon University, where he conducts research on social, knowledge, and transactive memory networks along with their effects on group and organizational learning and performance. Practical outcomes of his work include improved understanding of the impact of technology, offshoring, and turnover on organizational performance. Mr. Ashworth has won several prestigious grants from the Sloan Foundation and the National Science Foundation to pursue his research on transactive memory networks. Journals in which his research has appeared include Journal of Mathematical Sociology, International Journal of Human Resource Management, and Proceedings of the International Conference on Information Systems. His recent work on managing human resource challenges in the electric power industry has been featured in the Wall Street Journal and on National Public Radio's ``Morning Edition.' Mr. Ashworth received his undergraduate degree in systems engineering from the Georgia Institute of Technology. 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), a university-wide interdisciplinary center that brings together network analysis, computer science and organization science (www.casos.ece.cmu.edu). Prof. Carley carries out research that combines cognitive science, dynamic social networks, text processing, organizations, social and computer science in a variety of theoretical and applied venues. Her specific research areas are computational social and organization theory; dynamic social networks; multi-agent network models; group, organizational, and social adaptation, and evolution; statistical models for dynamic network analysis and evolution, computational text analysis, and the impact of telecommunication technologies on communication and information diffusion within and among groups. Prof. Carley has undergraduate degrees in economics and political science from MIT and a doctorate in sociology from Harvard University.     

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.     

Using an Iterated Prisoner's Dilemma with Exit Option to Study Alliance Behavior: Results of a Tournament and Simulation

Nearly half of all strategic alliances fail (Park and Russo, 1996; Dyer et al., 2001), often because of opportunistic behavior by one party or the other. We use a tournament and simulation to study strategies in an iterated prisoner's dilemma game with exit option to shed light on how a firm should react to an opportunistic partner. Our results indicate that a firm should give an alliance partner a second chance following an opportunistic act but that subsequent behavior should be contingent on the value of the next best opportunity outside the alliance. Firms should be more forgiving if the potential benefits from the alliance exceed other opportunities. The strategies were also found to be robust across a wide range of game lengths. The implications of these results for alliance strategies are discussed. Steven E. Phelan received his PhD in economics from La Trobe University (Australia) in 1998. Following five years at the University of Texas at Dallas, he joined the faculty of the University of Nevada Las Vegas in 2003. Dr. Phelan's research interests include competitive dynamics, organizational efficiency, acquisition and alliance performance, and entrepreneurial competence. His methods of choice to study these phenomena include agent-based modelling, experimental game theory, and event studies. Prior to joining academia, Dr. Phelan held executive positions in the telecommunications and airline industries and was a principal partner in Bridges Management Group, a consultancy specializing in strategic investment decisions. Richard J. Arend is a graduate of the University of British Columbia's doctoral program in Policy Analysis and Strategy. He is on the Management faculty of the University of Nevada, Las Vegas, arriving most recently from the Management faculty of New York University's Stern School of Business. Dr. Arend's interests lie in the analysis of unusual modes of firm value creation and destruction, where he has published in several top journals. He is a professional engineer with work and consulting experience in aerospace and computing. Darryl A. Seale joined the faculty of UNLV in 1999, following three years at Kent State University and the University of Alabama in Huntsville. Prior to Alabama, he completed his Ph.D. and M.S. degrees in Business Administration at the University of Arizona, his M.B.A. from Penn State University, and spent over ten years in management and market planning positions in the health care industry. Professor Seale's research interests include strategic decision making, bargaining and negotiation, and behavioral game theory. His research has been funded by the National Science Foundation and has been published in top-tier journals including Management Science, OBHDP, Games and Economic Behavior, and Strategic Management Journal. His teaching interests include business policy/strategy, managerial decision making, and bargaining and negotiation.     

Stable Outcomes for Two-Sided Contract Choice Problems

In this paper we study the cooperative theory of stable outcomes for the room-mates problem modeled as a contract choice problem. We show, that a simple generalization of the Deferred Acceptance Procedure with firms proposing due to Gale and Shapley (1962), yields outcomes for a two-sided contract choice problem, which necessarily belong to the core and are Weakly Pareto Optimal for firms. Under the additional assumptions: (a) given any two distinct workers, the set of yields achievable by a firm with the first worker is disjoint from the set of yields achievable by it with the second, and (b) the contract choice problem is pair-wise efficient, we prove that there is no stable outcome at which a firm can get more than what it gets at the unique outcome of our procedure.Somdeb Lahiri is a Professor of Microeconomic Theory at the School of Economic and Business Sciences, University of Witwatersrand at Johannesburg since May 2001. He received his Ph.D in Economic Theory from the University of Minnesota, Minneapolis in 1986. Subsequently he has been on the faculty of Indian Institute of Technology, Kanpur (January to May 1987) and Indian Institute of Management, Ahmedabad (May 1987 to May 2001). He has held visiting positions at the Indian Institute of Science Bangalore, the Indian Statistical Institutes at Delhi and Kolkata, INSEE Paris, Mc Master University and Mc Gill University. His research interests are in Social Choice theory, Cooperative Game theory and Axiomatic Economic Allocation theory.     

Diffusion dynamics in small-world networks with heterogeneous consumers

Diffusions of new products and technologies through social networks can be formalized as spreading of infectious diseases. However, while epidemiological models describe infection in terms of transmissibility, we propose a diffusion model that explicitly includes consumer decision-making affected by social influences and word-of-mouth processes. In our agent-based model consumers’ probability of adoption depends on the external marketing effort and on the internal influence that each consumer perceives in his/her personal networks. Maintaining a given marketing effort and assuming its effect on the probability of adoption as linear, we can study how social processes affect diffusion dynamics and how the speed of the diffusion depends on the network structure and on consumer heterogeneity. First, we show that the speed of diffusion changes with the degree of randomness in the network. In markets with high social influence and in which consumers have a sufficiently large local network, the speed is low in regular networks, it increases in small-world networks and, contrarily to what epidemic models suggest, it becomes very low again in random networks. Second, we show that heterogeneity helps the diffusion. Ceteris paribus and varying the degree of heterogeneity in the population of agents simulation results show that the more heterogeneous the population, the faster the speed of the diffusion. These results can contribute to the development of marketing strategies for the launch and the dissemination of new products and technologies, especially in turbulent and fashionable markets. This paper won the best student paper award at the North American Association for Computational Social and Organizational Science (NAACSOS) Conference 2005, University of Notre Dame, South Bend, Indiana, USA. Preceding versions of this paper have been presented to the Conference of the North American Association for Computational Social and Organizational Science (NAACSOS), 2005, University of Notre Dame, South Bend, USA and to the Conference of the European Social Simulation Association (ESSA), 2005, Koblenz, Germany. Sebastiano Alessio Delre received his Master Degree in Communication Science at the University of Salerno. After one year collaboration at the Institute of Science and Technologies of Cognition (ISTC, Rome, Italy), now he is a PhD student at the faculty of economics, University of Groningen, the Netherlands. His work focus on how different network structures affect market dynamics. His current application domain concerns Agent-Based Simulation Models for social and economic phenomena like innovation diffusion, fashions and turbulent market. Wander Jager is an associate professor of marketing at the University of Groningen. He studied social psychology and obtained his PhD in the behavioral and social sciences, based on a dissertation about the computer modeling of consumer behaviors in situations of common resource use. His present research is about consumer decision making, innovation diffusion, market dynamics, crowd behavior, stock-market dynamics and opinion dynamics. In his work he combines methods of computer simulation and empirical surveys. He is involved in the management committee of the European Social Simulation Association (ESSA). Marco Janssen is an assistant professor in the School of Human Evolution and Social Change and in the Department of Computer Science and Engineering at Arizona State University. He got his degrees in Operations Research and Applied Mathematics. During the last 15 years, he uses computational tools to study social phenomena, especially human-environmental interactions. His present research focuses on diffusion dynamics, institutional innovation and robustness of social-ecological systems. He combined computational studies with laboratory and field experiments, case study analysis and archeological data. He is an associate editor-in-chief of the journal Ecology and Society.     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.     

Introduction to normative multiagent systems

This article introduces the research issues related to and definition of normative multiagent systems. It also describes the papers selected from NorMAS05 that are part of this double special issue and relates the papers to each other. Guido Boella received the PhD degree at the University of Torino in 2000.He is currently professor at the Department of Computer Science of the University of Torino. His research interests include multi-agent systems, in particular, normative systems, institutions and roles using qualitative decision theory.He is the co-chair of the firstworkshops on normative multi-agent systems (NorMas05), on coordination and organization (CoOrg05), and the AAAI Fall Symposium on roles (Roles05). Leendert van der Torre received the Ph.D. degree in computer science fromErasmus University Rotterdam, The Netherlands, in 1997. He is currently a Full Professor at the University of Luxembourg. He has developed the so-called input/output logics and the BOID agent architecture. His current research interests include deontic logic, qualitative game theory, and security and coordination in normative multiagent systems. Harko Verhagen received his Ph.D. degree in computer and systems sciences from Stockholm University (Sweden) in 2000 and is currently an associate professor at the department. His research has focussed on simulation of organizational behaviour, simulation as a scientific method, the use of sociological theories in multiagent systems research and more in particular theories on norms and autonomy.     

A Dynamic Simulation Comparing Classical and Emergent-Network Models: Organizational Design Implications

In the last decade, organizations have spent more on the creation, transformation, and communication of information than on the production of physical goods. The information age has been ushered in by the widespread assimilation of information and communication technologies. Many contemporary practitioners and organizational theorists predict the demise of the classical organizational design because of its inability to accommodate the sociological change engendered by the information age.The current study advances an emergent-network model of organizational design and compares it to the classical approach through a dynamic simulation of prototypical organizational activities. Organizational activities approximating one year were simulated in each of five organizations under constant baseline conditions and over one hundred experimental design conditions. The emergent network model manifested higher levels of goal attainment, resource utilization, and organizational capacity for accommodating change. These findings suggest that organizations will benefit from conformance to the design principals of the emergent-network model.Bernard D. Hill Jr. earned his Ph.D. in Public Policy and Administration from Virginia Commonwealth University. He also holds a Master of Science in Business and a Bachelor of Science in Education. Bernard is currently employed as a Chief Information Officer with the Commonwealth of Virginia. He has held a broad array of technology leadership positions in both the public and private sectors and the academic arena. Bernard was selected as one of Computerworld’s Premier 100 IT Leaders for 2002. As CIO for the Virginia Department of Transportation, he also brokered a public-private partnership that won a nationwide Government Technology Leadership Award. This partnership provides security awareness training for employees in Virginia State government, as well as cities, counties, and localities throughout Virginia.Heinz Roland Weistroffer is an Associate Professor of Information Systems in the School of Business at Virginia Commonwealth University. Roland holds a Doctor of Science degree from the Free University Berlin, Germany, and a Master of Arts degree from Duke University. Previous appointments include Chief Research Officer at the Council for Scientific and Industrial Research in Pretoria, South Africa, and Senior Lecturer at the University of Natal in Durban, South Africa. Roland’s current research interests include computer assisted decision support, computer simulation modeling, object oriented modeling, and software engineering. He has published in IEEE Transactions on Software Engineering, IEEE Transactions on Systems, Man and Cybernetics, the Journal of Multi-Criteria Decision Analysis, and Socio-Economic Planning Sciences, among other journals.Peter Aiken is Director of the Institute for Data Research and an Associate Professor of Information Systems at Virginia Commonwealth University. His research has widely explored the area of data engineering and its relationship to systems and business reengineering. He is the author of Data Reverse Engineering and Clive Finkelstein’s co-author of Corporate Information Portals (McGraw-Hill 1996/99). His sixth book is titled XML in Data Management and is co-authored with David Allen. He has held leadership positions with the US Department of Defense and consulted with more than 50 organizations in 14 different counties. His research publications have appeared in the Communications of the ACM, IBM Systems Journal, IEEE Software and many others. He is a member of ACM, and the IEEE (Senior Member). He has been a DAMA International Advisor since 1999 and received their 2001 International Achievement Award. He has lectured internationally on these and related topics.     

Multi-objective optimization of mobile phone keymaps for typing messages using a word list

Most mobile phones today offer the option of using a word list to ease the typing of short messages (SMS). When a word list is used, a word is input as a sequence of digits by pressing the key corresponding to each letter once. The word list is used to look up the word(s) that correspond to this sequence of digits. This paper describes how a mobile phone keyboard layout can be obtained that is better suited for typing such messages. Two objectives are considered: the total cost of typing, and the total cost of word clashes that occur when a certain digit sequence corresponds to two or more words in the word list. A multi-start descent algorithm is developed to obtain a Pareto set of solutions.     

Unbordered partial words

An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word u can be written as a concatenation of nonempty prefixes of a word v, then u can be written as a unique concatenation of nonempty unbordered prefixes of v. We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).     

Abelian repetitions in partial words

We study abelian repetitions in partial words, or sequences that may contain some unknown positions or holes. First, we look at the avoidance of abelian pth powers in infinite partial words, where p>2, extending recent results regarding the case where p=2. We investigate, for a given p, the smallest alphabet size needed to construct an infinite partial word with finitely or infinitely many holes that avoids abelian pth powers. We construct in particular an infinite binary partial word with infinitely many holes that avoids 6th powers. Then we show, in a number of cases, that the number of abelian p-free partial words of length n with h holes over a given alphabet grows exponentially as n increases. Finally, we prove that we cannot avoid abelian pth powers under arbitrary insertion of holes in an infinite word.     

Maximal pattern complexity of higher dimensional words

This paper studies the pattern complexity of n-dimensional words. We show that an n-recurrent but not n-periodic word has pattern complexity at least 2k, which generalizes the result of [T. Kamae, H. Rao, Y.-M. Xue, Maximal pattern complexity of two dimension words, Theoret. Comput. Sci. 359 (1-3) (2006) 15-27] on two-dimensional words. Analytic directions of a word are defined and its topological properties play a crucial role in the proof.Accordingly n-dimensional pattern Sturmian words are defined. Irrational rotation words are proved to be pattern Sturmian. A new class of higher dimensional words, the simple Toeplitz words, are introduced. We show that they are also pattern Sturmian words.     

On highly palindromic words

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length-a power of the prevalent letter-we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word w by the ratio |rws|/|w|, where the word rws is minimal palindromic and rs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.     

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.