Communication and organizational social networks: a simulation model

Recent management research has evidenced the significance of organizational social networks, and communication is believed to impact the interpersonal relationships. However, we have little knowledge on how communication affects organizational social networks. This paper studies the dynamics between organizational communication patterns and the growth of organizational social networks. We propose an organizational social network growth model, and then collect empirical data to test model validity. The simulation results agree well with the empirical data. The results of simulation experiments enrich our knowledge on communication with the findings that organizational management practices that discourage employees from communicating within and across group boundaries have disparate and significant negative effect on the social network’s density, scalar assortativity and discrete assortativity, each of which correlates with the organization’s performance. These findings also suggest concrete measures for management to construct and develop the organizational social network.     

Data association based on optimization in graphical models with application to sensor networks

We propose techniques based on graphical models for efficiently solving data association problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful framework for representing the statistical dependencies among a collection of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes). We consider two different types of data association problems, corresponding to whether or not it is known a priori which targets are within the surveillance range of each sensor. We first demonstrate how to transform these two problems to inference problems on graphical models. With this transformation, both problems can be solved efficiently by local message-passing algorithms for graphical models, which solve optimization problems in a distributed manner by exchange of information among neighboring nodes on the graph. Moreover, a suitably reweighted version of the max–product algorithm yields provably optimal data associations. These approaches scale well with the number of sensors in the network, and moreover are well suited to being realized in a distributed fashion. So as to address trade-offs between performance and communication costs, we propose a communication-sensitive form of message-passing that is capable of achieving near-optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.     

Broadcast and gossip in line-communication mode

This paper addresses the problem of efficiently performing two important operations of communication in networks, namely broadcast and gossip. We study these operations in the line-communication model that is similar to the circuit-switching technique. We propose a simpler proof of the fundamental result, due to A. Farley, that gives the exact broadcast time, log₂ n steps, in any connected network of order n. In the second part we construct gossip algorithms in any tree network and we prove that they are optimal or asymptotically optimal. We finally give a precise idea of the shape of trees in which gossip is possible in log₂ n steps. Finally, we present general results on gossip in any connected graph.     

Cooperative metaheuristics for the permutation flowshop scheduling problem

In this work, we propose cooperative metaheuristic methods for the permutation flowshop scheduling problem considering two objectives separately: total tardiness and makespan. We use the island model where each island runs an instance of the algorithm and communications start when the islands have reached certain level of evolution, that is, communication is not allowed from the beginning of the execution. Subsequent ones occur when new better solutions are found. We carry out an exhaustive comparison of the cooperative methods against the sequential counterparts running in completely comparable scenarios. Results have been carefully analysed by means of statistical procedures and we can conclude that the cooperative methods yield much better results than the sequential algorithms and state-of-the-art methods running in the same number of processors but without communications. The proposed cooperative schemes are easy to apply to other algorithms and problems.     

Exploring communication networks to understand organizational crisis using exponential random graph models

In recent social network studies, exponential random graph (ERG) models have been used comprehensively to model global social network structure as a function of their local features. In this study, we describe the ERG models and demonstrate its use in modelling the changing communication network structure at Enron Corporation during the period of its disintegration. We illustrate the modelling on communication networks, and provide a new way of classifying networks and their performance based on the occurrence of their local features. Among several micro-level structures of ERG models, we find significant variation in the appearance of A2P (Alternating k-two-paths) network structure in the communication network during crisis period and non-crisis period. We also notice that the attribute of hierarchical positions of actors (i.e., high rank versus low rank staff) have impact on the evolution process of networks during crisis. These findings could be used in analyzing communication networks of dynamic project groups and their adaptation process during crisis which could lead to an improved understanding how communications network evolve and adapt during crisis.     

Probabilistic proximity searching algorithms based on compact partitions

The main bottleneck of the research in metric space searching is the so-called curse of dimensionality, which makes the task of searching some metric spaces intrinsically difficult, whatever algorithm is used. A recent trend to break this bottleneck resorts to probabilistic algorithms, where it has been shown that one can find 99% of the relevant objects at a fraction of the cost of the exact algorithm. These algorithms are welcome in most applications because resorting to metric space searching already involves a fuzziness in the retrieval requirements. In this paper, we push further in this direction by developing probabilistic algorithms on data structures whose exact versions are the best for high dimensions. As a result, we obtain probabilistic algorithms that are better than the previous ones. We give new insights on the problem and propose a novel view based on time-bounded searching. We also propose an experimental framework for probabilistic algorithms that permits comparing them in offline mode.     

Distributed colorings for collision-free routing in sink-centric sensor networks

When the environment does not allow direct access to disseminated data, a sensor network could be one of the most appropriate solutions to retrieve the map of interesting areas. Based on existing approaches, we start our study from the standard random deployment of a sensor network and then we consider a coarse-grain localization algorithm that associates sensors with coordinates related to a central node, called the sink. Once each sensor is associated with an estimated position, it starts to send data to the sink according to a designed schedule of communications that minimizes energy consumption and time by means of collisions avoidance. The outcome is a challenging combinatorial coloring problem for a specific graph class. We propose a schedule of communications based on distributed and fast coloring algorithms. The proposed solutions solve the underlying problems for the graphs of interest by means of an optimal, and in some cases near-optimal, number of colors. Finally, as the localization provides coarse-grain coordinates, different sensors might be associated with the same coordinates. Hence, in order to avoid that all such sensors perform the same actions (i.e., waste energy), a leader-election mechanism is considered.     

Bayesian Fused Lasso Regression for Dynamic Binary Networks

We propose a multinomial logistic regression model for link prediction in a time series of directed binary networks. To account for the dynamic nature of the data, we employ a dynamic model for the model parameters that is strongly connected with the fused lasso penalty. In addition to promoting sparseness, this prior allows us to explore the presence of change points in the structure of the network. We introduce fast computational algorithms for estimation and prediction using both optimization and Bayesian approaches. The performance of the model is illustrated using simulated data and data from a financial trading network in the NYMEX natural gas futures market. Supplementary material containing the trading network dataset and code to implement the algorithms is available online.     

Time series modeling of Army Mission Command communication networks: an event-driven analysis

We examine the communication time series of a fully-networked Army coalition command and control organization. The network comprised two echelons of command, at the Division and Brigade levels, over a 2-week military scenario exercise involving a Mission Command staff communicating over email and phone. We used time series analysis to predict the communications record based on an external work variable of the number of important scenario events occurring across time. After taking into account structural features of the time series—decreasing communications over time, a network crash, and the transition between weeks—we examined the remaining variability in email and phone communication. We found that the exercise scenario events were not a significant predictor of the Divisional communications, which were best fit by an auto-regressive model of order 1, meaning that the best predictor of the volume of communications at a given time point was the volume of communications on the immediately preceding time point. The occurrence of scenario events, however, did predict the Brigade communication time series, which were well fit by a lag dependent variable model. These results demonstrate that Brigade communications responded to and could be predicted by battlefield events, whereas the Division communications were only predicted by their own past values. These results highlight the importance of modeling environmental work events to predict organizational communication time series and suggest that network communications are perhaps increasingly dependent upon battlefield events for lower echelons of command closer to the tactical edge.     

A perspective on artificial intelligence: Learning to learn

The classical approach to the acquisition of knowledge in artificial intelligence has been to program the intelligence into the machine in the form of specific rules for the application of the knowledge: expert systems. Unfortunately, the amount of time and resources required to program an expert system with sufficient knowledge for non-trivial problem-solving is prohibitively large. An alternative approach is to allow the machine tolearn the rules based upon trial-and-error interaction with the environment, much as humans do. This will require endowing the machine with a sophisticated set of sensors for the perception of the external world, the ability to generate trial actions based upon this perceived information, and a dynamic evaluation policy to allow it to measure the effectiveness of its trial actions and modify its repertoire accordingly. The principles underlying this paradigm, known ascollective learning systems theory, have already been applied to sophisticated gaming problems, demonstrating robust learning and dynamic adaptivity.The fundamental building block of a collective learning system is thelearning cell, which may be embedded in a massively parallel, hierarchical data communications network. Such a network comprising 100 million learning cells will approach the intelligence capacity of the human cortex. In the not-too-distant future, it may be possible to build a race of robotic slaves to perform a wide variety of tasks in our culture. This goal, while irresistibly attractive, is most certainly fraught with severe social, political, moral, and economic difficulties.This paper was given as an invited talk on the 12th Symposium on Operations Research, University of Passau, September 1987.     

Neuroevolution strategies for episodic reinforcement learning

Because of their convincing performance, there is a growing interest in using evolutionary algorithms for reinforcement learning. We propose learning of neural network policies by the covariance matrix adaptation evolution strategy (CMA-ES), a randomized variable-metric search algorithm for continuous optimization. We argue that this approach, which we refer to as CMA Neuroevolution Strategy (CMA-NeuroES), is ideally suited for reinforcement learning, in particular because it is based on ranking policies (and therefore robust against noise), efficiently detects correlations between parameters, and infers a search direction from scalar reinforcement signals. We evaluate the CMA-NeuroES on five different (Markovian and non-Markovian) variants of the common pole balancing problem. The results are compared to those described in a recent study covering several RL algorithms, and the CMA-NeuroES shows the overall best performance.     

Structural learning of Bayesian networks by bacterial foraging optimization

Algorithms inspired by swarm intelligence have been used for many optimization problems and their effectiveness has been proven in many fields. We propose a new swarm intelligence algorithm for structural learning of Bayesian networks, BFO-B, based on bacterial foraging optimization. In the BFO-B algorithm, each bacterium corresponds to a candidate solution that represents a Bayesian network structure, and the algorithm operates under three principal mechanisms: chemotaxis, reproduction, and elimination and dispersal. The chemotaxis mechanism uses four operators to randomly and greedily optimize each solution in a bacterial population, then the reproduction mechanism simulates survival of the fittest to exploit superior solutions and speed convergence of the optimization. Finally, an elimination and dispersal mechanism controls the exploration processes and jumps out of a local optima with a certain probability. We tested the individual contributions of four algorithm operators and compared with two state of the art swarm intelligence based algorithms and seven other well-known algorithms on many benchmark networks. The experimental results verify that the proposed BFO-B algorithm is a viable alternative to learn the structures of Bayesian networks, and is also highly competitive compared to state of the art algorithms.     

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.     

Long-term characteristics of analogical processing in high-school students with high fluid intelligence: an fMRI study

Intelligence is known to predict scholastic achievement and enables high performance in cognitive tasks. Fluid intelligence is strongly related to analogical reasoning abilities, which are fundamental to mathematical thinking. Geometric analogical reasoning is a prototypical measure of fluid intelligence. However, the cerebral correlates of geometric analogical reasoning and their developmental modulation over time are still rarely investigated. We report a 1-year follow-up functional magnetic resonance imaging study of a geometric analogical reasoning task in high fluid intelligence high-school students. This study was designed to characterise the cerebral correlates of geometric analogical reasoning and to improve our knowledge about the impact of general cognitive development on behavioural performance and on cerebral mechanisms underlying geometric analogical reasoning in adolescents. Our data indicate that a fronto-parietal network comprising the left and right parietal lobes and the left middle frontal gyrus was equally modulated by task difficulty at both measuring time points. At the behavioural level, however, participants showed improvements in performance at the second measuring time point. The behavioural improvements point to a more efficient task processing. As this is not accompanied by differential recruitment of fronto-parietal brain regions, the data suggest an increase in neural efficiency for these brain regions.     

Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming

In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm does not perform well for this problem.     

Eigenspectral Analysis of Hermitian Adjacency Matrices for the Analysis of Group Substructures

In this paper we propose the use of the eigensystem of complex adjacency matrices to analyze the structure of asymmetric directed weighted communication.

The use of complex Hermitian adjacency matrices allows to store more data relevant to asymmetric communication, and extends the interpretation of the resulting eigensystem beyond the principal eigenpair. This is based on the fact, that the adjacency matrix is transformed into a linear self-adjoint operator in Hilbert space.

Subgroups of members, or nodes of a communication network can be characterised by the eigensubspaces of the complex Hermitian adjacency matrix. Their relative ‘traffic-level’ is represented by the eigenvalue of the subspace, and their members are represented by the eigenvector components. Since eigenvectors belonging to distinct eigenvalues are orthogonal the subgroups can be viewed as independent with respect to the communication behavior of the relevant members of each subgroup.

As an example for this kind of analysis the EIES data set is used. The substructures and communication patterns within this data set are described.     

Scheduling data transfers in a network and the set scheduling problem

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.     

Performance & packet traffic dynamics of Packet Switching Network model

Dynamics of packet traffic in data communication networks can be complex and often not well understood. Understanding of these complex dynamics is important for their control, prediction purposes and for the data networks design. The engineering community has described wired data networks architectures and studied them by means of a layered, hierarchical abstraction called ISO OSI (International Standard Organization Open System Interconnect) Reference Model. The Network Layer of the ISO OSI Reference Model is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using an abstraction of the Network Layer that we developed, we investigate packet traffic dynamics in our data network models of data communication networks of packet switching type, in particular near the phase transition point from free flow to congestion. We explore how these dynamics and network performance indicators are affected by network connection topology and routing algorithms. We consider static and adaptive routing algorithms. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

Information dynamics algorithm for detecting communities in networks

The problem of community detection is relevant in many scientific disciplines, from social science to statistical physics. Given the impact of community detection in many areas, such as psychology and social sciences, we have addressed the issue of modifying existing well performing algorithms by incorporating elements of the domain application fields, i.e. domain-inspired. We have focused on a psychology and social network-inspired approach which may be useful for further strengthening the link between social network studies and mathematics of community detection. Here we introduce a community-detection algorithm derived from the van Dongen’s Markov Cluster algorithm (MCL) method [4] by considering networks’ nodes as agents capable to take decisions. In this framework we have introduced a memory factor to mimic a typical human behavior such as the oblivion effect. The method is based on information diffusion and it includes a non-linear processing phase. We test our method on two classical community benchmark and on computer generated networks with known community structure. Our approach has three important features: the capacity of detecting overlapping communities, the capability of identifying communities from an individual point of view and the fine tuning the community detectability with respect to prior knowledge of the data. Finally we discuss how to use a Shannon entropy measure for parameter estimation in complex networks.