On effectiveness of wiretap programs in mapping social networks

Snowball sampling methods are known to be a biased toward highly connected actors and consequently produce core-periphery networks when these may not necessarily be present. This leads to a biased perception of the underlying network which can have negative policy consequences, as in the identification of terrorist networks. When snowball sampling is used, the potential overload of the information collection system is a distinct problem due to the exponential growth of the number of suspects to be monitored. In this paper, we focus on evaluating the effectiveness of a wiretapping program in terms of its ability to map the rapidly evolving networks within a covert organization. By running a series of simulation-based experiments, we are able to evaluate a broad spectrum of information gathering regimes based on a consistent set of criteria. We conclude by proposing a set of information gathering programs that achieve higher effectiveness then snowball sampling, and at a lower cost. Maksim Tsvetovat is an Assistant Professor at the Center for Social Complexity and department of Public and International Affairs at George Mason University, Fairfax, VA. He received his Ph.D. from the Computation, Organizations and Society program in the School of Computer Science, Carnegie Mellon University. His dissertation was centered on use of artificial intelligence techniques such as planning and semantic reasoning as a means of studying behavior and evolution of complex social networks, such as these of terrorist organizations. He received a Master of Science degree from University of Minnesota with a specialization in Artificial Intelligence and design of Multi-Agent Systems, and has also extensively studied organization theory and social science research methods. His research is centered on building high-fidelity simulations of social and organizational systems using concepts from distributed artificial intelligence and multi-agent systems. Other projects focus on social network analysis for mapping of internal corporate networks or study of covert and terrorist orgnaizations. Maksim’s vita and publications can be found on Kathleen M. Carley is a professor in the School of Computer Science at Carnegie Mellon University and the director of the center for Compuational Analysis of Social and Organizational Systems (CASOS) which has over 25 members, both students and research staff. Her research combines cognitive science, social networks and computer science to address complex social and organizational problems. Her specific research areas are dynamic network analysis, computational social and organization theory, adaptation and evolution, text mining, 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. She and her lab have developed infrastructure tools for analyzing large scale dynamic networks and various multi-agent simulation systems. The infrastructure tools include ORA, a statistical toolkit for analyzing and visualizing multi-dimensional networks. ORA results are organized into reports that meet various needs such as the management report, the mental model report, and the intelligence report. Another tool is AutoMap, a text-mining systems for extracting semantic networks from texts and then cross-classifying them using an organizational ontology into the underlying social, knowledge, resource and task networks. Her simulation models meld multi-agent technology with network dynamics and empirical data. Three of the large-scale multi-agent network models she and the CASOS group have developed in the counter-terrorism area are: BioWar a city-scale dynamic-network agent-based model for understanding the spread of disease and illness due to natural epidemics, chemical spills, and weaponized biological attacks; DyNet a model of the change in covert networks, naturally and in response to attacks, under varying levels of information uncertainty; and RTE a model for examining state failure and the escalation of conflict at the city, state, nation, and international as changes occur within and among red, blue, and green forces. She is the founding co-editor with Al. Wallace of the journal Computational Organization Theory and has co-edited several books and written over 100 articles in the computational organizations and dynamic network area. Her publications can be found at: http://www.casos.cs.cmu.edu/bios/carley/publications.php     

Limit cycles and update digraphs in Boolean networks

Boolean networks have been used as models of gene regulation and other biological networks, as well as for other kinds of distributed dynamical systems. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Salinas (2008) [22] and Aracena et al. (2009) [1], equivalence classes of deterministic update schedules according to the labeled digraph associated to a Boolean network (update digraph) were defined and it was proved that two schedules in the same class yield the same dynamical behavior. In this paper, we study the relations between the update digraphs and the preservation of limit cycles of Boolean networks iterated under non-equivalent update schedules. We show that the related problems lie in the class of NP-hard problems and we prove that the information provided by the update digraphs is not sufficient to determine whether two Boolean networks share limit cycles or not. Besides, we exhibit a polynomial algorithm that works as a necessary condition for two Boolean networks to share limit cycles. Finally, we construct some update schedule classes whose elements share a given limit cycle under certain conditions on the frozen nodes of it.     

The difference between common knowledge of formulas and sets

Common knowledge can be defined in at least two ways: syntactically as the common knowledge of a set of formulas or semantically, as the meet of the knowledge partitions of the agents. In the multi-agent S5 logic with either finitely or countably many agents and primitive propositions, the semantic definition is the finer one. For every subset of formulas that can be held in common knowledge, there is either only one member or uncountably many members of the meet partition with this subset of formulas held in common knowledge. If there are at least two agents, there are uncountably many members of the meet partition where only the tautologies of the multi-agent S5 logic are held in common knowledge. Whether or not a member of the meet partition is the only one corresponding to a set of formulas held in common knowledge has radical implications for its topological and combinatorial structure.     

Partitioning Signed Two-Mode Networks

Structural balance theory forms the foundation for a generalized blockmodel method useful for delineating the structure of signed social one-mode networks for social actors (for example, people or nations). Heider's unit formation relation was dropped. We re-examine structural balance by formulating Heider's unit formation relations as signed two-mode data. Just as generalized blockmodeling has been extended to analyze two-mode unsigned data, we extend it to analyze signed two-mode network data and provide a formalization of the extension. The blockmodel structure for signed two-mode networks has positive and negative blocks, defined in terms of different partitions of rows and columns. These signed blocks can be located anywhere in the block model. We provide a motivating example and then use the new blockmodel type to delineate the voting patterns of the Supreme Court justices for all of their nonunanimous decisions for the 2006–07 term. Interpretations are presented together with a statement of further problems meriting attention for partitioning signed two-mode data.     

Cost sharing of cooperating queues in a Jackson network

We consider networks of queues in which the independent operators of individual queues may cooperate to reduce the amount of waiting. More specifically, we focus on Jackson networks in which the total capacity of the servers can be redistributed over all queues in any desired way. If we associate a cost to waiting that is linear in the queue lengths, it is known from the literature how the operators should share the available service capacity to minimize the long run total cost. This paper deals with the question whether or not (the operators of) the individual queues will indeed cooperate in this way, and if so, how they could share the cost in the new situation such that each operator never pays more than his own cost without cooperation. For the particular case of a tandem network with two or three nodes it is known from previous work that cooperation is indeed beneficial, but for larger tandem networks and for general Jackson networks this question was still open. The main result of this paper gives for any Jackson network an explicit cost allocation that is beneficial for all operators. The approach we use also works for other cost functions, such as the server utilization.     

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.     

公平性与数学化(Ⅰ)选举理论

作者在这一系列文章中,将用不多的数学知识讨论由公平性问题派生出来的三个社会学课题：即选举理论,权力指数与公平分配。数学家的研究可以归结为这么一个结论：社会选择,一个难圆的梦。本篇讨论各种常用选举方法的利弊,并由此讨论选举理论中的一个重要的结果——Ａｒｒｏｗ定理：完全公平的选举系统不可能存在     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Achieving fully proportional representation by clustering voters

Both the Chamberlin–Courant and Monroe rules are voting rules that solve the problem of fully proportional representation: given a set of candidates and a set of voters, they select committees of candidates whose members represent the voters so that the voters’ total dissatisfaction is minimized. These two rules suffer from a common disadvantage, namely being computationally intractable. As both the Chamberlin–Courant and Monroe rules, explicitly or implicitly, partition voters so that the voters in each part share the same representative, they can be seen as clustering algorithms. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. Using ideas from cluster analysis we develop several approximation algorithms for the Chamberlin–Courant and Monroe rules and experimentally analyze their performance. We find that our algorithms are computationally efficient and, in many cases, are able to provide solutions which are very close to optimal.     

Brownian models of multiclass queueing networks: Current status and open problems

This paper is concerned with Brownian system models that arise as heavy traffic approximations for open queueing networks. The focus is on model formulation, and more specifically, on the formulation of Brownian models for networks with complex routing. We survey the current state of knowledge in this dynamic area of research, including important open problems. Brownian approximations culminate in estimates of complete distributions; we present numerical examples for which complete sojourn time distributions are estimated, and those estimates are compared against simulation.     

Finding the needles in the haystack: efficient intelligence processing

As a result of communication technologies, the main intelligence challenge has shifted from collecting data to efficiently processing it so that relevant, and only relevant, information is passed on to intelligence analysts. We consider intelligence data intercepted on a social communication network. The social network includes both adversaries (eg terrorists) and benign participants. We propose a methodology for efficiently searching for relevant messages among the intercepted communications. Besides addressing a real and urgent problem that has attracted little attention in the open literature thus far, the main contributions of this paper are two-fold. First, we develop a novel knowledge accumulation model for intelligence processors, which addresses both the nodes of the social network (the participants) and its edges (the communications). Second, we propose efficient prioritization algorithms that utilize the processor’s accumulated knowledge. Our approach is based on methods from graphical models, social networks, random fields, Bayesian learning, and exploration/exploitation algorithms.     

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.     

On Evolving Social Systems: Communication, Speciation and Symbiogenesis

In this paper we introduce three enhancements for evolutionary computing techniques in social environments. We describe the use of the genetic algorithm to evolve communicating rule-based systems, where each rule-based system represents an agent in a social/multi-agent environment. It is shown that the evolution of multiple cooperating agents can give improved performance over the evolution of an equivalent single agent, i.e. non-social, system. We examine the performance of two social system configurations as approaches to the control of gait in a wall climbing quadrupedal robot, where each leg of the quadruped is controlled by a communicating agent. We then introduce two social-level operators&2014;speciation and symbiogenesis&2014;which aim to reduce the amount of knowledge required a priori by automatically manipulating the system&2018;s social structure and describe their use in conjunction with the communicating rule-based systems. The reasons for implementing these kinds of operators are discussed and we then examine their performance in developing the controller of the wall-climbing quadruped. We find that the use of such operators can give improved performance over static population/agent configurations.     

Distributing evolutionary computation in a networked multi-agent environment

It has become increasingly popular to employ evolutionary algorithms to solve problems in different domains, and parallel models have been widely used for performance enhancement. Instead of using parallel computing facilities or public computing systems to speed up the computation, we propose to implement parallel evolutionary computation models on networked personal computers (PCs) that are locally available and manageable. To realize the parallelism, a multi-agent system is presented in which mobile agents play the major roles to carry the code and move from machine to machine to complete the computation dynamically. To evaluate the proposed approach, we use our multi-agent system to solve two types of time-consuming applications. Different kinds of experiments were conducted to assess the developed system, and the preliminary results show its promise and efficiency.     

Refined common knowledge logics or logics of common information

 In terms of formal deductive systems and multi-dimensional Kripke frames we study logical operations know, informed, common knowledge and common information. Based on [6] we introduce formal axiomatic systems for common information logics and prove that these systems are sound and complete. Analyzing the common information operation we show that it can be understood as greatest open fixed points for knowledge formulas. Using obtained results we explore monotonicity, omniscience problem, and inward monotonocity, describe their connections and give dividing examples. Also we find algorithms recognizing these properties for some particular cases. Received: 21 October 2000 / Published online: 2 September 2002 Key words or phrases: Multi-agent systems – Non-standard logic – Knowledge representation – Common knowledge – Common information – Fixed points, Kripke models – Modal logic     

Reward systems for intra-organizational knowledge sharing

Knowledge sharing is one of the most critical steps in knowledge management activities. To achieve effective knowledge sharing, it is important to encourage workers to share their knowledge for the best interests of the firm. However, successfully exerting this encouragement is very challenging. In this paper, we develop a formal model and analyze reward systems for intra-organizational knowledge sharing. Specifically, two common forms of reward systems are considered; individual-based reward which is based on the individual contribution of valuable knowledge, and group-based reward which is based on the contribution of the whole group through knowledge sharing to the firm performance. Through the analysis, we derive a simple optimal individual-based reward system which depends on the amount and the productivity of shared knowledge. The system balances the benefit from knowledge sharing of each worker with the costs related with it. Next, it is found that group-based reward is not only less efficient than individual-based reward, but it also subject to a potential productivity problem, in which workers with more productive knowledge do not participate in knowledge sharing. Finally, it is shown that several organizational factors can complement reward systems in increasing the performance of KM and can mitigate the productivity problem. Insights from our analysis could help managers to understand important considerations in rewarding knowledge sharing, and could provide them with guides to implement reward systems.     

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.     

Consensus of heterogeneous multi-agent systems with linear and nonlinear dynamics

In this paper, we perform an in-depth study about the consensus problem of heterogeneous multi-agent systems with linear and nonlinear dynamics.Specifically, this system is composed of two classes of agents respectively described by linear and nonlinear dynamics. By the aid of the adaptive method and Lyapunov stability theory, the mean consensus problem is realized in the framework of first-order case and second-order case under undirected and connected networks.Still, an meaningful example is provided to verify the effectiveness of the gained theoretical results. Our study is expected to establish a more realistic model and provide a better understanding of consensus problem in the multi-agent system.     

The categorical approach to social choice theory

A number of different problems in social choice theory are given a common treatment in the framework of category theory. A social choice function is a map μ from a set Hom(A, PX) of profiles - in applications functions from a set A of agents to the set PX of linear orders on a set X of alternatives - to a set GPX the nature of which depends on the application. The main theorem established is applied to social welfare functions and strategy-proof voting schemes.     

Leaving us in tiers: can homophily be used to generate tiering effects?

Substantial evidence indicates that our social networks are divided into tiers in which people have a few very close social support group, a larger set of friends, and a much larger number of relatively distant acquaintances. Because homophily—the principle that like seeks like—has been suggested as a mechanism by which people interact, it may also provide a mechanism that generates such frequencies and distributions. However, our multi-agent simulation tool, Construct, suggests that a slight supplement to a knowledge homophily model—the inclusion of several highly salient personal facts that are infrequently shared—can more successfully lead to the tiering behavior often observed in human networks than a simplistic homophily model. Our findings imply that homophily on both general and personal facts is necessary in order to achieve realistic frequencies of interaction and distributions of interaction partners. Implications of the model are discussed, and recommendations are provided for simulation designers seeking to use homophily models to explain human interaction patterns.