Saswati Mukherjee

Matangini Chattopadhyay
email: matanginic@gmail.com

Samiran Chattopadhyay
email: samirancju@gmail.com

Debarshi Kumar Sanyal

Roshni Neogy

Samanwita Pal

A Novel Incentive Based Scheme to Contain Selective Forwarding in Wireless Sensor Network

Keywords: Wireless Sensor Network, Selective Forwarding, Random Graphs, Virtual Currency, Throughput, Network Security

Selective forwarding or dropping of packets is a serious threat to multi hop communication in a Wireless Sensor Network (WSN). There are various schemes to induce cooperation in a WSN to overcome this problem. In this paper, we have introduced a novel adversary model and have proposed an incentive based scheme to inspire cooperation among nodes in a WSN. The scheme has been formally analyzed. The efficacy of the scheme is also established through various simulation experiments.

Introduction

Nodes in mobile ad-hoc networks are arbitrarily deployed without relying on any fixed network infrastructure. In a multi-hop wireless network, many pairs of nodes cannot communicate directly and must forward data to each other via one or more intermediate forwarding nodes.

Multi-hop communication is not an issue where nodes faithfully forward packets according to a global algorithm. Selfish nodes may like to send their own packets but may not be ready to relay packets for others since relaying packets for others consumes bandwidth and energy. This, in turn, decreases both individual and system throughput and might even lead to loss of connectivity in a network.

Hence, cooperation among the nodes needs to be enforced. The basic aim of any such mechanism is to force nodes to forward packets sent to it by other nodes. There are many proposed solutions [START_REF] Felegyhazi | Nash equilibria of packet forwarding strategies in wireless ad hoc networks[END_REF][START_REF] Mukherjee | Addressing Forwarder's Dilemma: A Game-Theoretic Approach to Induce Cooperation in a Multi-Hop Wireless Network[END_REF] which use game theoretic and graph theoretic notions to examine whether cooperation can exist in multi-hop communication while many solutions are proposed based on providing incentives. Incentives can be positive or negative. That is, a node can be made to cooperate within a network either by providing some incentive or by taking punitive actions against a node when its rate of packet forwarding falls below a particular value. Marti et al. [START_REF] Michiardi | CORE: A COllaborative REputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF] have discussed schemes to identify misbehaving nodes (non-forwarders) and deflect traffic around them. Michiardi and Molva [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks[END_REF] have devised reputation mechanisms where nodes observe the behavior of others and prepare reputation reports. Zhong et al. [START_REF] Buttyan | Enforcing service availability in mobile ad-hoc WANs[END_REF] proposed the use of currencies to enforce cooperation. Buttyan and Hubaux [START_REF] Buttyaan | Nuglets: a virtual currency to stimulate cooperation in selforganized mobile ad hoc networks[END_REF][START_REF] Bansal | Observation-based Cooperation Enforcement in Ad Hoc Net-works[END_REF] devised a scheme based on a virtual currency called a nuglet that a node pays to send its own packets but receives, if it forwards other's packets.

In all these papers, nodes are classified in two categories: trusted those who forward packets and malicious, those who do not like to forward others' packets. Moreover, malicious nodes, according to these papers are content by dropping packets to conserve their resources. In this paper, we have introduced two further dimensions to this misbehavior model. First, we introduced a 'rational adversary' category of nodes. 'Rational adversary nodes' do not mind dropping packets if they are not penalized for that. Second, we have incorporated an idea by which 'malicious' nodes inspire their neighboring nodes to drop packets.

In this paper, we have also proposed design of a point based credit scheme in a fairly dense sensor network that encourages nodes to cooperate in packet forwarding and thereby contains selective forwarding and restores throughput of the network. In the proposed scheme, nodes that forward packets get incentives in the form of credit points. Nodes that drop packets to conserve resources are penalized by deducting credit points from them. Malicious nodes may send 'bribe' packets to neighbouring nodes to inspire them to drop packets. If a 'bribe' packet reaches a trusted node, the sender node is stripped of a good number of credit points. Credit point reserve of any node may not go below a threshold limit. The network is considered as an undirected graph with flat/unstructured topology. In flat topology each sensor node performs similar functions like packet forwarding data sensing with some exceptions in their behaviour as defined by the adversary model.

We have shown that if the graph is sufficiently dense then the likelihood of detecting malicious nodes is very high. We have also proposed an algorithm which helps to use the proposed scheme when the network is less dense. If the proposed scheme is allowed to run then simulation results suggest that the throughput of the network remains considerably high as long as the numbers of rational adversary nodes are less in proportion. Message overhead is low with small number of trusted and rational adversary node despite having large number of malicious nodes. The proposed scheme achieves scalability even if the number of nodes gets increased. Although the basic approach assumes a dense network, we have also presented a mechanism by which our scheme continues to work in less dense networks.

The remainder of this paper is organized as follows. Section 2 presents the related research work. In Section 3, the model definitions of the proposed work are described. Section 4 presents algorithmic view of the proposed scheme. In this section, we have also analyzed the scheme analytically. In Section 5, experimental results are presented to measure the performance of our proposed method. Finally, we draw our conclusion.

Related Work

The work to enforce cooperation in mobile and wireless ad hoc network is based on providing incentives while other works are reputation and trust based. Some others are formalized in game theoretic framework. In this section, we review some important reputation based and incentive based schemes.

CORE [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks[END_REF], CONFIDANT [START_REF] Zhong | Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks[END_REF], OCEAN [START_REF] Salem | A charging and rewarding scheme for packet forwarding in multi-hop cellular networks[END_REF] are examples of reputation and trust based systems. In CORE and CONFIDANT systems, non-cooperative nodes are detected by using certain reputation measures. In CONFIDANT, the reputation of noncooperative nodes is propagated throughout the network for punishment. In CORE, nodes with bad reputation are gradually removed from the network. CORE consists of two basic components: a watchdog mechanism and a reputation table. The watchdog mechanism is used to detect misbehavior nodes but the disadvantage is that it not only creates a performance bottleneck by increasing network congestion, transmission overhead etc. but also diminishes the network scalability. OCEAN, another trust based method, has five components to detect non-cooperative nodes and mitigate the risk of selective forwarding. The overhead to calculate trust or reputation values is a common severe problem of these methods.

Buttyan and Hubaux [START_REF] Buttyaan | Nuglets: a virtual currency to stimulate cooperation in selforganized mobile ad hoc networks[END_REF][START_REF] Bansal | Observation-based Cooperation Enforcement in Ad Hoc Net-works[END_REF] proposed the concept of providing incentives to the nodes in a static wireless ad hoc network so that they faithfully forward packets. According to this scheme, nodes get paid for sending packets to other nodes. The 'money' used in this scheme is termed as Nuglets. The scheme is implemented using two models: The Packet Purse Model and Packet Trade Model. In Packet Purse Model, the originator of the packet pays for the packet forwarding service. The originator loads it with the number of nuglets sufficient to reach the destination. Each forwarding node acquires one or several nuglets from the packet and thus, increases its stock of nuglets. If the packet does not have enough nuglets to be forwarded, the packet is discarded. The problem with this model is that estimating the number of nuglets to be loaded with the packet is difficult. In Packet Trade Model, the packet is traded for nuglets by intermediate nodes. Each intermediary buys it from previous one for some nuglets and sells it to the next one for more nuglets. A basic disadvantage of this model is that packet flooding is possible. This scheme requires tamper proof hardware for reliably calculating the nuglet distribution.

Sheng Zhong et al. [START_REF] Buttyan | Enforcing service availability in mobile ad-hoc WANs[END_REF] proposed a scheme called Sprite, a simple cheat-proof credit based system. In Sprite, a Credit Clearance Service (CCS) is introduced to determine the charge and credit to each node involved in message transmission. When a node receives a message, the node keeps a receipt of the message and later reports it to the CCS. This scheme requires a central server to determine the charge and credit to each node involved in message transmission.

Salem et al. [START_REF] Jakobsson | A micropayment scheme encouraging collaboration in multi-hop cellular networks[END_REF] proposed another incentive mechanism based on charging and rewarding scheme which forces selfish nodes to rationally opt for forwarding packets. Their proposal provides a set of protocols that rely on symmetric cryptography techniques.

In [START_REF] Erdős | On the Evolution of Random Graphs[END_REF], Jackobson and others have proposed a micro-payment scheme for multihop cellular networks that encourages collaboration in packet forwarding. In this paper, an asymmetric communication model is assumed.

The scheme presented in this paper uses the basic concept of incentives as discussed in [START_REF] Buttyan | Enforcing service availability in mobile ad-hoc WANs[END_REF][START_REF] Buttyaan | Nuglets: a virtual currency to stimulate cooperation in selforganized mobile ad hoc networks[END_REF][START_REF] Bansal | Observation-based Cooperation Enforcement in Ad Hoc Net-works[END_REF]. But our paper differs from them in many ways. First, our paper introduces a new adversary model in a fairly dense static wireless sensor network which is richer than the one proposed in all these papers. Second, our scheme is distributed with minimal overhead. Third, simulation results are provided to show that the scheme is scalable and effective.

Model Definitions

In this section, we give a clear definition of the proposed models and the reasons why we have chosen this model. Since we are studying cooperation in packet forwarding, we assume that the main reason for packet losses in the network is the noncooperative behavior of the nodes.

Adversarial Model

We have identified primarily two types of non-cooperative nodes: faulty or malicious or misbehaved and selfish or rational adversary. Faulty/malicious activity refers to that class of misbehavior where nodes try to attack the system. They threaten the entire network by dropping packets in order to conserve their resources and by inspiring neighbors not to forward packets. As our scheme is based on credit point system where points are to be acquired by every node, the sanctity of the credit points in each node is essential. The misbehaved nodes are assumed to be capable of manipulating the credits available in the non-trusted neighbors around them. This is modeled by the malicious nodes being able to send "bribe" packets to their neighbors. A bribe packet offers certain points to its receivers. By receiving a bribe packet, a selfish node may drop some packets without jeopardizing its stock of points.

The adversary is rational, in the sense that it will only attempt to cheat if the expected benefit of doing so is greater than the expected benefit of acting honestly in network related operations. Naturally, if a rational adversary node is offered a "bribe" packet to increase its credit point, it will actually accept it as long as there is no harm in accepting it.

The third category of nodes is termed trustworthy or trusted. They refer to the class of well-behaved nodes that functions reliably and honestly throughout the network operations.

Network Model

We have considered a wireless network containing N nodes and the nodes are divided in three categories as explained in the Adversary model. The topology of the wireless sensor network is basically an undirected graph where an edge between two nodes denotes that they can communicate with each other. The topology is flat as these nodes are homogeneous except in their capability defined by the adversary model.

The network is modeled as an "Uncorrelated random graph (Erdős-Rényi)" [START_REF] Das | Routing in Ad-hoc Networks Using Minimum Connected Dominating Sets[END_REF] where N nodes are connected through n edges which are chosen randomly from the N(N-1)/2 possible configurations. The probability of selecting an edge is p.

Point Based Credit Scheme

A Point Based credit mechanism of charging/rewarding the service (which is forwarding a packet in this case) is presented to stimulate node cooperation in ad-hoc networks. In this section, we give a formal description of proposed Point Based credit scheme.

 All the nodes in the network are initialized with some credit points.  Nodes earn credit points as rewards if they forward packets.  Nodes lose credit point as penalty if they do not forward packets.  Credit points assigned to all the nodes must not fall below a specified threshold value.  Trustworthy nodes always forward packets and earn points and hence they always help in increasing the network throughput.  Bribe packets are offered by the malicious/misbehaving nodes to random neighboring nodes inspiring them to drop packets in order to pull down the network efficiency. Every bribe packet contains a certain number of points. These points are deducted from the stock of points of the malicious nodes.  The rational adversary nodes on receiving the bribe packets check if its accumulated points are above the threshold value. If so, then they do not forward packets so long as points accumulated by accepting bribe packets are more than points lost due to not forwarding packets. Otherwise, they forward packets and earn credit points as rewards.  A malicious/misbehaving node forwards packet if it's accumulated credit point falls below the threshold.  Trustworthy nodes on receiving bribe packets from malicious nodes penalize them by deducting points. The execution of the proposed charging/rewarding scheme requires tamper proof hardware [START_REF] Buttyaan | Nuglets: a virtual currency to stimulate cooperation in selforganized mobile ad hoc networks[END_REF][START_REF] Bansal | Observation-based Cooperation Enforcement in Ad Hoc Net-works[END_REF] to monitor the addition or deduction of points assigned to the nodes or requires a central server to assess the charge involved or credit points of each node for message transmission. Thus, we do not assume any MAC layer misbehavior.

Algorithmic Description of the Proposed Scheme

The proposed scheme has two phases: Network Deployment and Charging/Rewarding Service.

Network Deployment Phase

Step 1: Input the number of nodes for each class of nodes.

Step 2: Assign equal credit points E to all the nodes. Step 3: Set threshold limit T of credit point to all the nodes.

In the for loop, Step A and Step B run in parallel.

Analysis of Algorithm

For a random graph with n number of nodes, suppose that the probability of choosing an edge is p. That is, p, fraction of the total number of edges is selected randomly in such a graph. It is known that in such a graph, as n tends to infinity, the probability that a graph of n vertices with edge probability p = 2ln (n)/n is connected, tends to 1.

It is also known that the average degree of a node in such random graph is np with variance npq where q = 1-p.

In our case, n = (n1+n2 +n3) where n1, n2, n3 denote the number of malicious nodes, rational adversary nodes and trustworthy nodes respectively. Thus, the average number of edges from any node to a trusted node is n 3 p. However, this is the mean value. The connectivity of any node to a trusted node may decrease from the mean value by the square root of the variance. Thus, the following inequality must hold to maintain connectivity to a trusted node from any given node.

npq p n  3 (1)
Solving the inequality, we get,

2 3 / ) 1 /( n n p p   (2)

Algorithm PACKET_FORWARDING_SCHEME For (;;) {

Step A.

The MALICIOUS nodes send out a number of "bribe" packets depending on the amount of its stock of points to randomly selected neighbouring nodes.

On receiving a packet

Step B.

) 1 /( k k p   (3)
Therefore, if the fraction of edges in the network is greater than k/(1+k) then it is likely that a malicious node is always connected to some trusted node. In such a scenario, the bribe packet randomly sent out by a malicious node would reach the trusted node some time and the malicious node will surely be penalized.

Finding positions of additional trusted nodes

The proposed scheme heavily depends on a misbehaved node being connected with at least one trusted node in its neighborhood. So, the network becomes dense. In a given deployment, it may so happen that each malicious node does not have a trusted node as its neighbor. In such situations, we can adopt the following scheme to deploy additional trusted nodes if necessary so that every malicious node is ensured to be connected to a trusted node. Our approach is based on Minimum Connected Dominating Set of the network.

We have made some additional assumptions to handle the case where each malicious node is not connected directly to a trusted node. These assumptions are as follows. The trusted nodes are assumed to be deployed with a key for secured communication. All nodes are assumed to be equipped with location information. Location information of a node denotes information about its spatial coordinates in a given area.

The following algorithm determines the locations where additional trusted nodes should be deployed so that direct edge connectivity between a malicious node and a trusted node is ensured.

If the graph contains n nodes then Step 1, Step 2 can be performed in O(n) [START_REF] Sinha | MCEDER: Multicast Core-Extraction Distributed Ad-hoc Routing[END_REF] time. If the approximate MCDS of G contains h number of nodes then Step 3a, Step 4a can be performed in O(h) time [START_REF] Pandana | Cooperation enforcement and learning for optimizing packet forwarding in autonomous wireless networks[END_REF]. Step 3b.and Step 4b takes O(h 2 ) time. Step 5 can be performed in O(h) time.

Algorithm FindPositionsOfAdditionalTrustedNodes

Input: The Graph G describing the topology of the wireless sensor network Output: Locations where additional trusted nodes should be deployed Step 1:

Let T = set of trusted nodes. Let u be a designated trusted node. // These nodes have a key for secured communication.

Step 2:

Find an approximate Minimum Connected Dominating Set (MCDS) C of G starting with T using a standard greedy algorithm in the literature.

Step 3a: u broadcasts a message asking for the location information from each node in C.

Step 3b:

u receives the location information from all nodes. Step 4:

u broadcasts a challenge message to all nodes in C u receives responses only from the trusted nodes.

Step 5:

u finds out the locations of the nodes in C which are not trusted and writes them in P Step 6: return P Experimental Analysis

A simulation experiment is performed with a by considering a number of random graphs having 100 wireless nodes and 1000 edges. In a given topology, there would be many different possibilities of mixes of trustworthy nodes, misbehaved nodes and rational adversary nodes. In order to model these varieties, we have chosen ten sets of different ratios of these three classes of wireless nodes as shown in Figure 1. The rational behind the choice of different sets is as follows. Suppose we fix a small number of trusted nodes, say 20, in the network. Keeping this number fixed, we can choose several numbers of malicious nodes. Suppose that, the number of malicious nodes is chosen to be 20, 40, 60 and 80. Once the number of trusted nodes and malicious nodes are fixed, the number of rational adversary nodes can be computed. Next, we increase the number of trusted nodes to 40 and continue the same process. For every set, a number of random graphs are generated in our experiment.

The PACKET_FORWARDING_SCHEME algorithm is executed in terms of rounds where each round signifies time duration. There are several parameters in the algorithm. In our experiments, parameters of the algorithm are assigned with the following values.

 Each node is initialized with 15 credit points.  Each node earns 1 credit point as reward if it forwards a packet.  Each node is penalized by 1.5 credit point if it drops a packet.  Misbehaved nodes are penalized with 2 points by the trusted node, if the trusted node receives a bribe packet from the misbehaved node.  Offer in the "BRIBE" is set at 0.1 percent of the points owned by the malicious nodes sending the bribe packet  Threshold credit point of a node is 7.5.

In the experiments throughput is defined as the number of packets dropped to number of packets generated. Detection ratio is defined as the ratio of the number of MALICIOUS nodes detected to the actual number of MALICIOUS nodes in the network.

─ Throughput measurement in the face of selective forwarding In Figure 2, throughput is plotted against different proportion of trusted, misbehaved and rational adversary nodes. Recall that ten different compositions of trusted, rational adversary and misbehaved nodes are considered as shown in Figure 1.

We can see that the throughput drops for Set 1 and Set 5. We also note that this is because in both these sets, the number of rational adversary nodes is considerable. As the number of rational adversary nodes is significant, misbehaved nodes can offer many "bribe" packets to them. These bribe packets induces rational adversary nodes not to forward packets resulting in a drop in throughput.

In the presence of less number of rational adversary nodes, throughput is improved even if there are a small number of trusted nodes compared to the number of malicious nodes. This is observed for Set 4, Set 7, Set 9, and Set 10. Figure 5 shows the relationship between the number of rounds with the number of nodes to detect all malicious nodes. We have chosen three combinations of three types of nodes as defined by Set 1, Set 2 and Set 3. It can be seen that the number of rounds to detect all malicious nodes remains almost the same even if the number of nodes is increased.

Figure 6 plots average number of messages exchanged per node when number of nodes increase for various compositions of 3 types of nodes. The average numbers of message exchanges are not growing rapidly with respect to the number of nodes. Thus, it can be claimed that the scheme is scalable. In Figure 7, we have tried to capture the effect of the number of rational adversary nodes keeping the number of trusted nodes to 20. The number of misbehaved nodes is changed. Accordingly, the number of rational adversary nodes increase as the total numbser of nodes is kept at 100. It is observed that throughput steadily increases as the number of rational adversary nodes decrease (and the number of misbehaved nodes increase). Fig. 6. Average number of messages exchanged for all sets having different compositions of nodes (as mentioned in Figure 1)

We can also verify the same from Figure 2. You may recall that the proportion of rational adversary nodes is more in the Sets 1, 2, 5, 3, 6, 8 in a non-increasing order. Throughput values for these sets in the graph reflect that the presence of rational adversary nodes bring throughput down.

Conclusion

In the paper, we have introduced a new adversary model for Wireless Sensor Networks. In this model, the idea of rational adversary nodes is floated in addition to trusted and malicious nodes. An incentive based scheme is presented to induce cooperation among nodes to solve the problem of selective forwarding. The scheme is analyzed and studied through simulation experiments.

The incorporation of rational adversary nodes introduces new twists to the problem. As a future work, we need to study further the effect of such nodes in throughput. We also plan to invent a trace algorithm which can detect malicious nodes even when it is not directly connected to some trusted node.

Fig. 1 .

 1 Fig. 1. Different sets of nodes with various proportions of trusted, misbehaved and rational adversary nodes in the Network.

Fig. 2 .

 2 Fig. 2. Throughput of 10 sets of sensor nodes having different proportions of trusted, rational adversary, and malicious nodes

Fig. 3 . 5 ─

 35 Fig. 3. Throughput after increasing number of rounds for Set 5

Fig. 4 .

 4 Fig. 4. Message Exchange overhead for all sets of combination of 3 types of node

Fig. 5 .

 5 Fig. 5. Number of rounds required for 100% detection of misbehaved nodes with various number of nodes ─ Effect of rational adversary nodes

Fig. 7 .

 7 Fig. 7. Effect of rational adversaries with respect to throughput

Acknowledgements. The work proposed is supported in part by UGC-UPE Phase II program of Jadavpur University.


Štěpán Kuchař
email: stepan.kuchar@vsb.cz

Jan Martinovič
email: jan.martinovic@vsb.cz

Pavla Dráždilová
email: pavla.drazdilova@vsb.cz

Kateřina Slaninová
email: katerina.slaninova@vsb.cz

Synthetic Social Network Based on Competency-based Description of Human Resources

Keywords: Synthetic social network, Complex network, Human resource management, Competency model

The approach presented in this paper is based on the field of human resource management with the aim to extend the analysis of human resources by a graph theory perspective with an output representation by synthetic social networks. Further analysis of human resources is focused on their division into communities with similar competencies and skills. We used betweenness concept of centrality for finding important persons in the network that share their skills and competencies with workers in other communities and can therefore serve as contact persons between communities with different skills. This method can also be used for suggesting worker team composition based on similarity of workers' skills for different roles.

Introduction

A typical social network is as a set of people, or groups of people, who socially interact among themselves [START_REF] Newman | Networks: An Introduction[END_REF]. In these networks the relations are usually defined by one of the types of interaction between the actors, e.g. personal knowledge of one another, friendship, membership, etc. However, in the area of synthetic social networks, we can explore the extended definition of social networks. This can be done by exploring social network as a set of people, or groups of people who have similar patterns of contacts of interactions, or generally with similar attributes [START_REF] Radicchi | Defining and identifying communities in networks[END_REF].

This approach can then be extended to the analysis of complex networks. Complex networks, especially in the web sphere and internet areas, are often called synthetic, or derived, social networks [START_REF] Musiałl | Social networks on the internet[END_REF]. This type of social network differs from natural social networks due to the relationship between the nodes. They are generated on the basis of the common attributes of the nodes [START_REF] Costa | Characterization of complex networks: A survey of measurements[END_REF]. These attributes do not necessarily represent the physical communication or the interaction among objects like in the natural social networks [START_REF] Bisgin | Investigating homophily in online social networks[END_REF], but other attributes representing the personal similarity. The approach presented in this paper is based on these types of networks and the relations between workers based on similar skills and competencies.

The approach presented in the paper is based on the field of human resource management with the aim to extend the analysis and simulation of human resources in business processes by a graph theory perspective with an output representation by synthetic social networks (because real social relations and interactions between individual workers are not known). The relation to this special type of social networks can lead to further analysis of human resources focused on their thorough division into communities based on similar skills and competencies. This step is not possible without usage of the social network approach. Due to this reason, the issues of social network area are described and defined in this paper, including social network evaluation and community detection field. On the basis of performed analyses, the experiments which detect latent ties between particular resources are presented. The relations between human resources are defined not only by their similarity, but also by their membership in communities with similar behaviour.

Due to the fact, that the proposed approach consists of two different application areas, the structure of the paper is following. In Section Social Network, the area of social networks with evaluation and community detection is described. Section Competencybased description of human resources focuses on human resources and their competency description. This section ends with the description of connection between vector model for human resources and graph theory approach of synthetic social networks. Afterwards, Section Experiments with experiments is presented, which describes usage of social network analysis focused on human resource management. Social network evaluation is used for gaining new information about relations between human resources and for analysis of resources with interesting properties and behaviour.

Social Network

Social networking is a complex, large and expanding sector of the information economy. Researchers' interest in this field is growing rapidly. It has been studied extensively since the beginning of the 20th century. The first normative contributions in this area were proposed in 1970s by sociologist Mark Granovetter and mathematician Linton C. Freeman. The basic theory "The Strength of Weak Ties" was mentioned in 1973 [START_REF] Granovetter | The Strength of Weak Ties[END_REF]. Granovetter argued that within a social network, weak ties are more powerful than strong ties. Another significant principle was published in 1979 by Linton C. Freeman [START_REF] Freeman | Centrality in social networks: Conceptual clarification[END_REF]. In his work was presented definition of centrality, which is one node's relationship to other nodes in the network. He defined basic metrics like degree, control and independence, from which reason researchers proceed in their present works.

Social network is a set of people or groups of people with similar patterns of contacts or interactions such as friendship, co-working, or information exchange [START_REF] Garton | Studying online social networks[END_REF]. The World Wide Web, citation networks, human activity on the internet, physical and biochemical networks are some examples of social networks. Social networks are usually represented by using graphs, where nodes represent individuals or groups and lines represent contacts among them. The configuration of relations among network members identifies a specific network structure, and this structure can vary from isolated structures where no members are connected to saturated structures in which everyone is interconnected.

A relationship between the actors in a social network can be very complex, often making them multidimensional. This fact leads to the formation of various types of social networks. Amongst others, we can mention multi-layered social networks (with homogeneous nodes, but with multiple relations), bipartite social networks (with two types of nodes), multi-modal social networks (with many types of nodes), temporal social networks (which reflect the network evolution), or multidimensional social networks, in which are combined a hierarchy of relations with a group hierarchy of nodes, and a time dimension [START_REF] Kazienko | Multidimensional social network: Model and analysis[END_REF].

Social network analysis was defined by Barry Wellman as "work at describing underlying patterns of social structure, explaining the impact of such patterns on behavior and attitudes" [START_REF] Knoke | Social network analysis[END_REF]. Therefore, researchers are not interested only on describing the different social structures, but they emphasize on investigating the consequences of this variation on the member's behaviors.

Evaluation of Social Networks

For a description of social networks defined in 1979, see Linton Freeman [START_REF] Freeman | Centrality in social networks: Conceptual clarification[END_REF] various types of centrality, where individual network nodes are directly evaluated, or where the average value of selected centrality in a graph may be an item of interest.

A primary use of graph theory in social network analysis is to identify the important or prominent actors at both the individual and group levels of analysis. Centrality and prestige concepts and measures seek to quantify graph theoretic ideas about an actor's prominence within a complete network by summarizing the structural relations among all nodes. Centrality means that a prominent actor has high involvement in many relations, regardless of whether sending or receiving ties. Prestige is when a prominent actor initiates few relations but receives many directed ties. Knoke and Yang defined the above mentioned terms in [START_REF] Knoke | Social Network Analysis[END_REF].

Degree centrality requires the usage of matrix algebra notation. Unlike actor degree centrality, group degree centralization measures the extent to which the actors in a social network differ from one another extent to which the actors in a social network differ from one another in their individual degree centralities.

Closeness centrality was developed to reflect how near a node is to the other nodes in a social network [START_REF] Sabidussi | The centrality index of a graph[END_REF]. Closeness and distance refer to how quickly an actor can interact with others, for example, by communicating directly or through very few intermediaries. An actor's closeness centrality is a function of its geodesic distance (length of the shortest path connecting the two nodes) to all other nodes.

Betweenness concept of centrality concerns how other actors control or mediate the relations between two nodes that are not directly connected. Actor betweenness centrality measures the extent to which other actors lie on the geodesic path between pairs of actors in the network.

To understand networks and their participants, we provide the location of actors in the network. Measuring the network location is finding the centrality of a node. These measures determine the various roles and groupings in a network -who are the connectors, specialists, leaders, bridges, isolates, where are the clusters and who is in them, who is in the core of the network, and who is on the periphery.

Community Detection

The discovery and analysis of community structure in networks is a topic of considerable recent interest in sociology, physics, biology and other fields. Networks are very useful as a foundation for the mathematical representation of a variety of complex systems such as biological and social systems, the Internet, the world wide web, and many others [START_REF] Newman | The Structure and Dynamics of Networks: (Princeton Studies in Complexity)[END_REF]. A common feature of many networks is community structure, the tendency for vertices to divide into groups, with dense connections within groups and only sparser connections between them [START_REF] Girvan | Community structure in social and biological networks[END_REF].

Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] proposed algorithms for finding and evaluating community structure in network. They used a divisive technique which iteratively removes edges from the network, thereby breaking it up in communities. The edges to be removed are identified by using one of a set of edge betweenness measures, of which the simplest is a generalization to edges of the standard shortest-path betweenness of Freeman. Than, their algorithms include a recalculation step in which betweenness scores are re-evaluated after the removal of every edge.

To detect communities, graph partitioning methods or hierarchical clustering has been applied. Originally, graph partitioning methods, based on edge removal [START_REF] Pothen | Partitioning sparse matrices with wigenvectors of graphs[END_REF], divide the vertices of a network into a given number of (non-overlapping) groups of a given size, while the number of edges between groups is minimal.

Spectral Clustering

Spectral clustering is one of the divisive clustering algorithms which can be applied in the graph theory. The spectral clustering algorithm uses eigenvalues and eigenvectors of a similarity matrix derived from the data set to find the clusters. In this section, there is described the type of spectral clustering based on the second smallest eigen vector of the Laplacian matrix.

Given a set of data points {x 1 , . . . x n } ∈ R m and similarity (cosine measure) a i j ≥ 0 between all pairs of the data points x i and x j . Let G = (V, E) be an undirected graph with vertex set V = {v 1 , . . . , v n }. Each vertex v i in this graph represents the data point x i . Two vertices are connected, if the similarity a i j between the corresponding data points x i and x j is positive, and the edge is weighted by a i j . The weighted adjacency matrix of the graph is the matrix A = (a i j ) i, j = 1, . . . , n. If a i j = 0 than (v i , v j ) / ∈ E(G). It governs that A is symmetric for the undirected graph. The degree of a vertex v i ∈ V is defined as d i = n ∑ j=1 a i j . The degree matrix D is defined as the diagonal matrix with the degrees d 1 , . . . , d n on the diagonal. The unnormalized graph of Laplacian matrix is defined as L = D -A. In [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF], Fiedler defines the second smallest eigenvalue a(G) of the of Laplacian matrix L(G) as algebraic connectivity of the graph G. In his honor, the corresponding eigenvector is called Fiedler vector. The Spectral Partitioning Algorithm which uses Fiedler vector is summarized in [START_REF] Pothen | Partitioning sparse matrices with wigenvectors of graphs[END_REF]. We used algorithm for spectral clustering (Left-Right algorithm) which is described in article [START_REF] Drázdilová | Spectral clustering: Left-right-oscillate algorithm for detecting communities[END_REF].

Competency-Based Description of Human Resources

The description of the employees' skills in the process is a human resources management area of expertise where the competency models [START_REF] Dreyfus | A five-stage model of the mental activities involved in directed skill acquisition[END_REF][START_REF] Ennis | Competency models: a review of the literature and the role of the employment and training administration (ETA)[END_REF][START_REF] Sinnott | Competencies: Report of the competencies workgroup, workforce and succession planning work groups[END_REF] and skills frameworks (e.g. Skills Framework for the Information Age [START_REF]SFIA Foundation: Framework reference SFIA version 4G[END_REF]) are used. Competency models define various competencies which are important for the company and its processes. Competencies are defined as sets of knowledge, abilities, skills and behaviour that contribute to successful job performance and the achievement of organizational results [START_REF] Sinnott | Competencies: Report of the competencies workgroup, workforce and succession planning work groups[END_REF]. Skills frameworks have the same purpose, but they describe skills particular for one domain rather than general competencies. But in fact skills are just a special type of competencies.

Competency models and skills frameworks also describe how to measure and evaluate individual competencies. In most cases competencies are measured by a number of advancing stages where higher levels of competency include everything from their lower levels. The first competency model had five stages [START_REF] Dreyfus | A five-stage model of the mental activities involved in directed skill acquisition[END_REF] and later models used the same system, but they did not keep the number of stages. There is no standard for how many stages should a competency model have and every model defines its own set of stages.

Therefore, competencies of a specific human resource can be described by the competency level acquired by the resource. This also means that this resource has mastered this given level and all lower levels of the competency. This way it is not important how many levels does the competency model have because the computing model can assume, that the highest acquired level of the best resource is also the highest level of the competency model.

Let's have a small example of one Developer working in a software development company. His competencies in a 10-level model could look as follows:

-Java development -7. level, -C# development -2. level, -UML knowledge -4. level, communication -2. level, customer knowledge of VSB-TUO -4. level, customer knowledge of MyCompany -0. level. Domain specific skills (development, UML knowledge), general competencies (communication) and knowledge of the environment (customer knowledge) are contained in this example. It is clear that competencies in the model have to be based on the company requirements and professional domain.

Competency-based Description of Process Activity Requirements

All activities in the process also have competency-based requirements that describe what competencies should the worker performing the activity know. Therefore, each activity will be defined by the set of competency levels for each required resource type entering the activity specifying that only workers with given or higher level will do the activity as planned. Resources with lower competencies are able to finish the activity, but it will take additional time to learn how to perform the activity and their work is prone to contain more errors. A simple example of requirements for the activity of developing customer specific code in the software development company follows:

-Development -6. level, -UML knowledge -3. level, communication -3. level, customer knowledge -4. level. If we compare this example with the worker example from previous chapter, one can notice the generalization of some requirements (development and customer knowledge). When assessing the employee's competencies, it is better to define the competency levels in specific parts of the domain so that the resources are assessed as precisely as possible. On the other hand, the activity requirements should only define a level for the whole competency category, and relevant part of the domain will be specified by actual process case. In other words, if the development company tackles with a case where they have to develop a Java code for the company VSB-TUO, then the requirements in this case will be refined as Java development and customer knowledge of VSB-TUO.

Competency Models and Synthetic Social Network

To create a synthetic social network based on the competencies of human resources, similarities between these resources had to be evaluated. This evaluation was performed using vector space model that is very often used in document searches [START_REF] Berry | Survey of text mining: clustering, classification, and retrieval[END_REF]. To use this model for the competencies, a way to describe the resource competencies as vectors had to be found. This was solved by devising fragmented vector representation of the competency levels for given resource. This representation and its different properties and validation was described in our previous work (see [START_REF] Kuchar | Human Resource Allocation in Process Simulations Based on Competency Vectors[END_REF]).

On the basis of created vector model, similarity matrix M H×H can be constructed for the set of resources R. The matrix contains similarities of particular resources from range of values < 0, 1 >. It is suitable to filter vertices between resources, which are of lower importance, for construction of synthetic social network and for further finding of communities. For this purpose, the threshold λ is defined. Afterwards, it is possible to construct graph G(R, E), where E represents a strength of vertices between particular resources, while weights w ∈ E meet the constraint w ≥ λ . After construction of graph G, we can find community resources with similar attributes. In the proposed approach, we use Left-Right Algorithm for community detection, described in Section Spectral Clustering. The output set of communities C is used in further experiments.

Experiments

For the experiment, we created a synthetic social network for the workers involved in a software process of a local middle-sized software development company. 8 roles were identified in the process and their possible competency level intervals were specified based on the process requirements and several selected worker profiles (competency profiles were not available for all workers in the process). Then, 143 competency profiles were created based on these constraints, each containing 19 competencies important in the software process, and each on a 10-level scale. 41 basic activities were analysed in the process and their requirements were specified for the same 19 competencies to ensure their compatibility.

The network in this experiment was created by using the similarities between competency profiles specifying individual human resources in the process. The threshold λ for creating the network was set to 0.7 to filter insignificant connections that cluttered the network.

Visualization of Detected Communities

The first added value that the created network brought was the possibility to detect communities of workers in the process based on their competencies. Communities shown in Fig. 1 were detected by the Left-Right Algorithm described in Section Spectral Clustering. The algorithm detected eight distinct communities: Administrators, Analysts & Designers, CRM Managers, Database Specialists, Java Developers, .NET Developers, Project Managers and Testers. These communities are very similar to the roles in the process except for one combined community for both Analysts and Designers (showing that these two roles are very similar in their competencies) and two separate communities for two types of managers that were defined as one role in the process. Even though these roles were known prior to the experiment, it showed that this detection algorithm could be effectively used for discerning roles in the environment without predefined roles.

Evaluation of Betweenness Centrality

One of the interesting evaluation method of the social networks is betweenness centrality (see Section Evaluation of Social Networks) that specifies how much a node in the network links other nodes together. When considering the network based on competency similarities, betweenness identifies universal workers that have acquired knowledge from multiple disciplines. These workers can serve as communication bridges among different communities. Betweenness centrality for individual workers is proportionally displayed in Fig. 2.

Tester15 has the biggest betweenness centrality for obvious reasons because he connects the community of Testers with the Java developers and .NET developers communities. Administrator6 and Administrator7 create a similar link between Administrators and Java and .NET developers. On the other hand, JavaDeveloper19 creates a bridge between a lot of Java developers and Administrators. Analyst4 and Analyst5 connect Managers with Analysts & Designers and other communities.

Analysis of Connections to Different Communities

All prior analyses considered the network as a whole, but very interesting results can be gained by looking at individual workers in the process. The network connects resources with similar competencies and with similar knowledge. Therefore, connected individuals can understand each other more easily because they share common knowledge and common behaviour. Analysing these connections for a specific worker can lead to finding people in other communities that could make a more effective team or that could be used for easier acquisition of additional knowledge from another part of the process. This information could also be used for choosing more appropriate worker for performing an activity because his hidden knowledge and easier collaboration could help him to understand the domain more quickly.

Process activities and their competency requirements play an important role in this analysis because the correct choice of appropriate worker is primarily based on these requirements. Table 1 contains the number of neighbouring resources for each resource that is suitable for the System Architecture Analysis activity for the process case specialized on MSSQL database for VSB-TUO customer. This table is separated into several sections based on the similarity threshold that was used to look for neighbouring nodes for each resource. The resources are sorted according to their competency suitability to perform the specified activity, Analyst3 being the most suitable and Analyst4 being still able to perform the activity but having to spent more time with the activity. The neighbourhood analysis shows that even though Analyst5 is the third in suitability, his knowledge similar to one of the Database Specialists could help him some specific difficulties concerning an analysis of heavily database-centric system and therefore it could be a better match for such task. On the other hand, Analyst3 could be a better match for a process case concerning Javarelated specifics because he could simplify the further work on the design by providing language-related hints to the architecture analysis document.

In considering the team composition, not only number of neighbours is important, but actual neighbouring workers have to be identified. These neighbours share common knowledge and could find a better ground at understanding each other when collaborating even though they have not met before. Fig. 3 shows neighbouring workers for the Analyst4 worker.

Conclusion and future work

A new method for using the synthetic social networks in the field of allocating human resources and finding suitable representatives for other spheres of human activities was presented in this paper. The experiments proved the hypothesis that selected human resources have relation to other sources, which are oriented not only to queried resource and similar activities, but to other activities as well. Many neighbouring resources are classified into other communities and this information can be used to enhance the communication between different parts of the process. Moreover, the betweenness centrality evaluation detected resources that create bridges between communities obtained by our developed Left-Right algorithm.

In future work, presented results will be used for identifying teams that will be able to collaborate more effectively due to their common knowledge [START_REF] Fitzpatrick | Forming effective worker teams with multi-functional skill requirements[END_REF][START_REF] Karduck | Forming the optimal team of experts for collaborative work[END_REF][START_REF] Wi | A team formation model based on knowledge and collaboration[END_REF]. We intend to use extended queries by several fields and obtained knowledge about community overlapping. This means that selected worker may be important not only for his own community but that he may have relations to other communities as well.

Based on presented results, a combination of social network analysis and human resources field can provide added value for human resource allocation, collaboration and decision support processes.

Fig. 1 .

 1 Fig. 1. Communities in the Competency-based Synthetic Social Network

Fig. 2 .

 2 Fig. 2. Betweenness Centrality Evaluation

Fig. 3 .

 3 Fig. 3. Neighbours of the Analyst4 Resource

Table 1 .

 1 Number of Neighbours for Resources Suitable for the System Architecture Analysis-MSSQL,VSB-TUO Activity

	Resource	Own community		Neighbouring communities
		Analysts &	.NET	CRM	Java	Project Database
		Designers	Developers Managers Developers Managers Specialists
		Similarity threshold = 0.7
	Analyst3	17	5	2	2	2
	Analyst1	17	2	1	1
	Analyst5	17	5	3		4	1
	Analyst4	16	4	4	1	3	1
		Similarity threshold = 0.75
	Analyst3	17	1	2		1
	Analyst1	9	2
	Analyst5	10	2	2		1
	Analyst4	11	2
		Similarity threshold = 0.8
	Analyst3	5	1
	Analyst1	4
	Analyst5	6	1
	Analyst4	4
		Similarity threshold = 0.85
	Analyst3	4
	Analyst1	1
	Analyst5	3
	Analyst4	1

Acknowledgments. This work was partially supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070) and by SGS, VSB -Technical University of Ostrava, Czech Republic, under the grant No. SP2013/167 Analysis of the behaviour patterns in complex networks.


Micha L Woźniak
email: michal.wozniak@pwr.wroc.pl

Application of combined classifiers to data stream classification

Keywords: machine learning, classifier ensemble, data stream, concept drift, incremental learning, forgetting

The progress of computer science caused that many institutions collected huge amount of data, which analysis is impossible by human beings. Nowadays simple methods of data analysis are not sufficient for efficient management of an average enterprize, since for smart decisions the knowledge hidden in data is highly required, as which multiple classifier systems are recently the focus of intense research. Unfortunately the great disadvantage of traditional classification methods is that they "assume" that statistical properties of the discovered concept (which model is predicted) are being unchanged. In real situation we could observe so-called concept drift, which could be caused by changes in the probabilities of classes or/and conditional probability distributions of classes. The potential for considering new training data is an important feature of machine learning methods used in security applications or marketing departments. Unfortunately, the occurrence of this phenomena dramatically decreases classification accuracy.

Introduction

Designing such solutions we should take into consideration that in the modern world the most of the data arrive continuously and it causes that smart analytic tools should respect this nature and be able to interpret so-called data streams. They should take into consideration that:

the statistical dependencies among the observations of given objects and their classifications could change, data can come flooding in the analyzer what causes that it is impossible to label all records. This phenomena is called concept drift [START_REF] Widmer | Learning in the presence of concept drift and hidden contexts[END_REF] and it comes in many forms, depending on the type of change. In general, the following approaches can be considered to deal with the mentioned above problem -Rebuilding a classification model if new data becomes available, which is very expensive and impossible from a practical point of view, especially if the concept drift occurs rapidly.

-Detecting concept changes in new data and if these changes are sufficiently "significant", then rebuilding the classifier. -Adopting an incremental learning algorithm for the classification model. We will concentrate on the last proposition. Adapting the learner is a part of an incremental learning [START_REF] Muhlbaier | Learn ++ .nc: Combining ensemble of classifiers with dynamically weighted consult-and-vote for efficient incremental learning of new classes[END_REF]. The model is either updated (e.g., neural networks) or needs to be partially or completely rebuilt (as CVFDT algorithm [START_REF] Hulten | Mining time-changing data streams[END_REF]). Usually we assume that the data stream is given in a form of data chunks. When dealing with the sliding window the main question is how to adjust the window size. On the one hand, a shorter window allows focusing on the emerging context, though data may not be representative for a longer lasting context. On the other hand, a wider window may result in mixing the instances representing different contexts. Therefore, certain advanced algorithms adjust the window size dynamically depending on the detected state (e.g., FLORA2 [START_REF] Widmer | Learning in the presence of concept drift and hidden contexts[END_REF]) or algorithms can use multiple windows [START_REF] Lazarescu | Using multiple windows to track concept drift[END_REF]. One of the important group of algorithms dedicated to stream classification exploits strength of ensemble systems, which work pretty well in static environments [START_REF] Kuncheva | Combining Pattern Classifiers: Methods and Algorithms[END_REF], because according to "no free lunch theorem" [START_REF] Wolpert | The supervised learning no-free-lunch theorems[END_REF] there is not a single classifier that is suitable for all the tasks, since each of them has its own domain of competence. A strategy for generating the classifier ensemble [START_REF] Wozniak | A survey of multiple classifier systems as hybrid systems[END_REF] should guarantee its diversity improvement and consequently accuracy increasing. Let us enumerate the main propositions how to get a desirable set of individual classifiers:

-The individual classifiers could be train on different datasets, because we hope that classifiers trained on different inputs would be complementary. -The individual classifiers can use the selected features only.

-Usually it could be easy to decompose the classification problem into simpler ones solved by the individual classifier. The key problem of such approach is how to recover the whole set of possible classes. -The last and intuitive method is to use individual classifiers trained on different models or different versions of models.

Combined classifier

According to Wolpert's no free lunch theorem there is not a single pattern recognition algorithm that is appropriate for all the tasks we are faced with, since each classifier has its own domain of competence [START_REF] Wolpert | The supervised learning no-free-lunch theorems[END_REF].

Usually we have a pool of different classifiers at our disposal to solve a given problem. Therefore, methods that can exploit the strengths of individual classifiers are the focus of intense research [START_REF] Jain | Statistical pattern recognition: a review. Pattern Analysis and Machine Intelligence[END_REF]. There are many relevant works formulated conclusions regarding combined classification quality, such as [START_REF] Hansen | Neural network ensembles. Pattern Analysis and Machine Intelligence[END_REF] where a neural network ensemble was considered or [START_REF] Xu | Methods of combining multiple classifiers and their applications to handwriting recognition[END_REF] where authors dealt with majority voting applied to handwriting recognition. Turner [START_REF] Tumer | Analysis of decision boundaries in linearly combined neural classifiers[END_REF] showed that averaging outputs of an infinite number of unbiased and independent classifiers can lead to the same response as the optimal Bayes classifier. Ho [START_REF] Ho | Decision combination in multiple classifier systems[END_REF] underlined that a decision combination function must receive useful representation of each classifier's decision. Specifically, they considered several method based on decision ranks, such as Borda count. Finally, the landmark works devoted introducing bagging [START_REF] Breiman | Bagging predictors[END_REF] and boosting [START_REF] Schapire | The strength of weak learnability[END_REF][START_REF] Freund | Boosting a weak learning algorithm by majority[END_REF] which are able to produce strong classifiers [START_REF] Kearns | An introduction to computational learning theory[END_REF], in the (Probably Approximately Correct) theory [START_REF] Angluin | Queries and concept learning[END_REF] sense, on the basis of the weak ones.

It is important to notice that the classifier ensemble design does not differ from that of a classical pattern recognition [START_REF] Giacinto | Design of effective multiple classifier systems by clustering of classifiers[END_REF] application, in which we select the most valuable features and choose the best classification method from the set of available ones. The design of a classifier ensemble aims to create a set of complementary/diverse classifiers and assign an appropriate combination method of individual classifier outputs as well as possible. We have to mention Ho's work [19] who distinguished two main approaches:

-Coverage optimization focus on the generation of a set of mutually complementary classifiers which can be combined to achieve optimal accuracy using a fixed decision combination function. -Decision optimization concentrates on designing and training an appropriate decision combination function while a set of individual classifier is given in advance [START_REF] Roli | In: Design of Multiple Classifier Systems[END_REF]. We can distinguish the important issues that must be taken into consideration when building classifier ensemble grouping them into the following problems:

-Proposing the topology i.e., interconnections among individual classifiers in the ensemble. -Selecting a pool of diverse and complementary individual classifiers for the ensemble. -Designing a combination rule, aimed at creating a mechanism that can exploit the strengths of the selected classifiers. Let's focus on the problem of forming a valuable pool of classifiers called ensemble pruning. Selecting members of classifier ensemble with different kinds of components is a key feature of considered system design, because we have to notice that apart from increasing the computational complexity, combining similar classifiers should not contribute much to the combined classifier under construction. An ideal ensemble includes mutually complementary individual classifiers which are characterized by the high diversity and accuracy [START_REF] Krogh | Neural network ensembles, cross validation, and active learning[END_REF], because we expect that combined classifier accuracy increases according to the diversity increasing of individual classifier pool [START_REF] Zenobi | Using diversity in preparing ensembles of classifiers based on different feature subsets to minimize generalization error[END_REF]. First, classifiers must be selected to obtain positive results from their fusion. In [START_REF] Sharkey | Combining diverse neural nets[END_REF] Sharkley et al. proposed four level of diversity based on the majority voting rule answer, coincident error, and possibility of at least one correct answer of ensemble members. Brown et al. [START_REF] Brown | Diversity creation methods: a survey and categorisation[END_REF] reflected that it is not appropriate for the case where diversity of an ensemble is differ in differ subspace of the feature space.

Classifier ensembles for data stream

Among the most popular ensemble approaches, the following are worth noting: the Streaming Ensemble Algorithm (SEA) [START_REF] Street | A streaming ensemble algorithm (sea) for large-scale classification[END_REF] or the Accuracy Weighted Ensemble (AWE) [START_REF] Wang | Mining concept-drifting data streams using ensemble classifiers[END_REF]. Both algorithms keep a fixed-size set of classifiers. Incoming data are collected in data chunks, which are used to train new classifiers. If there is a free space in the ensemble, a new classifier joins the committee. Otherwise, all the classifiers are evaluated based on their accuracy and the worst one in the committee is replaced by a new one if the latter has higher accuracy. The SEA uses a majority voting strategy, whereas the AWE uses the more advanced weighted voting strategy. A similar formula for decision making is implemented in the Dynamic Weighted Majority (DWM) algorithm [START_REF] Kolter | Dynamic weighted majority: a new ensemble method for tracking concept drift[END_REF]. Nevertheless, unlike the former algorithms, the DWM modifies the weights and updates the ensemble in a more flexible manner. The weight of the classifier is reduced when the classifier makes an incorrect decision. Eventually the classifier is removed from the ensemble when its weight falls below a given threshold. Independently, a new classifier is added to the ensemble when the committee makes a wrong decision. The final group consists of algorithms that address the question of when drift occurs. Not all classification algorithms dealing with concept drift, require drift detection. Some evolving systems continuously adjust the model to incoming data [START_REF] Zliobaite | Change with delayed labeling: When is it detectable?[END_REF]. This technique is called implicit drift detection [START_REF] Kuncheva | Classifier ensembles for detecting concept change in streaming data: Overview and perspectives[END_REF] as opposed to explicit drift detection methods that raise a signal to indicate change. The detector can be based on changes in the probability distribution of the instances [START_REF] Gaber | Classification of changes in evolving data streams using online clustering result deviation[END_REF][START_REF] Markou | Novelty detection: a review-part 1: statistical approaches[END_REF][START_REF] Salganicoff | Density-adaptive learning and forgetting[END_REF] or classification accuracy [START_REF] Klinkenberg | Detecting concept drift with support vector machines[END_REF][START_REF] Baena-García | Early drift detection method[END_REF]. Among the machine learning methods dealing with concept drift, a new class has recently emerged [START_REF] Ramamurthy | Tracking recurrent concept drift in streaming data using ensemble classifiers[END_REF], comprising algorithms that process data streams featuring a recurring context. Two additional requirements are imposed on algorithms in this class:

the system should maintain knowledge of previously emerged contexts, and it should be effective in recognizing contexts and switching to a valid one.

Both issues can be effectively solved by an ensemble system. For example, in [START_REF] Ramamurthy | Tracking recurrent concept drift in streaming data using ensemble classifiers[END_REF] the authors propose collecting context oriented learners in a "global set" of classifiers along with their selection procedure. The ensemble consists of classifiers that achieve arguably better results than a random classifier. To address the second issue, certain algorithms use a conceptual representation of contexts. This idea originates from Turney's definition of context-sensitive features [START_REF] Turney | Exploiting context when learning to classify[END_REF] and the early work by Widmer [START_REF] Widmer | Tracking context changes through meta-learning[END_REF] on meta-learning algorithms. It is based on mapping attributes into contextual clues representing some characteristic features of the respective context. In [START_REF] Gomes | Learning recurring concepts from data streams with a context-aware ensemble[END_REF], the authors exploit an additional similarity measure between context representations for weighting a classifier's contribution to the ensemble. The method presented in [START_REF] Katakis | Tracking recurring contexts using ensemble classifiers: an application to email filtering[END_REF] incorporates a stream clustering algorithm, which aims to group incoming data batches automatically based on their conceptual representation. An incremental classifier is created (and updated if needed) for each cluster/context and stored in the pool. A similar solution can be found in [START_REF] Hosseini | Pool and accuracy based stream classification: A new ensemble algorithm on data stream classification using recurring concepts detection[END_REF], but here classifiers in the pool are adaptively weighted according to their performance on a recent data batch.

Exemplary combined algorithm for data stream classification

We assume that the classified data stream is given in a form of data chunks denotes as DS k , where k is the chunk index. The concept drift could appear in the incoming data chunks. We do not detect it, but we try to construct self-adapting classifier ensemble. Therefore on the basis of the each chunk one individual is trained and we check if it could form valuable ensemble with the previously trained models. In our algorithm we propose to use the Generalized Diversity (denoted as GD) proposed by Partridge and Krzanowski [START_REF] Partridge | Software diversity: practical statistics for its measurement and exploitation[END_REF] to assess all possible ensembles and to choose the best one. GD returns the maximum values in the case of failure of one classifier is accompanied by correct classification by the other one and minimum diversity occurs when failure of one classifier is accompanied by failure of the other.

GD(Π) = 1 - L ∑ i=1 i(i -1)pi L(L -1) L ∑ i=1 ipi L ( 1
)
where L is the cardinality of the classifier pool (number of individual classifiers) and pi stands for the probability that i randomly chosen classifiers from Π will fail on randomly chosen example. We can also use modification of GD called Coincident Failure Diversity (CF D) is the modification of Generalized Diversity proposed by Partridge and Krzanowski as well [START_REF] Partridge | Software diversity: practical statistics for its measurement and exploitation[END_REF] CF

D(Π) =    0 p0 = 1 1 1-p 0 n ∑ l=1 n-l n-1 p l p0 < 1 (2)
It returns 0 if the pool Π is not diverse and 1 if each classifier errs on different example. Lets Pa(Ψi) denotes frequency of correct classification of classifier Ψi and itter(Ψi) stands for number of iterations which Ψi has been spent in the ensemble. We propose to establish the classifier's weight w(Ψi) according to the following formulae

w(Ψi) = Pa(Ψi) √ itter(Ψi) (3)
This proposition of classifier aging has its root in object weighting algorithms where an instance weight is usually inversely proportional to the time that has passed since the instance was read [START_REF] Klinkenberg | Adaptive information filtering: Learning in the presence of concept drifts[END_REF] and Accuracy Weighted Ensemble (AWE) [START_REF] Wang | Mining concept-drifting data streams using ensemble classifiers[END_REF], but the proposed method called Weighted Aging Ensemble (WAE) incudes two important modifications:

1. classifier weights depend on the individual classifier accuracies and time they have been spending in the ensemble, 2. individual classifier are chosen to the ensemble on the basis on the non-pairwise diversity measure. The WAE pseudocode is presented in Alg.1 [START_REF] Wozniak | Application of combined classifiers to data stream classification[END_REF].

Algorithm 1 Weighted Aging Ensemble (WAE)

Require: input data stream, data chunk size, classifier training procedure, ensemble size L 1: i := 1 2: repeat 3: collect new data chunk DSi 4:

train classifier Ψi on the basis of DSi 5:

add Ψi to the classifier ensemble Π 6:

if i > L then 7:

Ψ k+1 = Ψi 8: Πt = ∅ 9:
GDt = 0 10: i := i + 1 26: until end of the input data stream

for j = 1 to L + 1 do 11: if GD(Π\Ψi) (calculated

Experimental investigations

In this section we will present an illustrative example of WAE for a data stream classification problem. The aims of the experiment were to assess if the proposed method of weighting and aging individual classifiers in the ensemble is valuable proposition compared with the methods which do not include aging or weighting techniques.

Set-up

All experiments were carried out on the SEA dataset describes in [START_REF] Street | A streaming ensemble algorithm (sea) for large-scale classification[END_REF]. For each of the experiments we decided to form homogenous ensemble i.e., ensemble which consists of the Naive Bayes classifiers. During each of the experiment we tried to evaluate dependency between data chunk sizes (which were fixed on 50, 100, 150, 200) and overall classifier quality (accuracy and standard deviation) for the following ensembles:

1. w0a0 -an ensemble using majority voting without aging.

2. w1a0 -an ensemble using weighted voting without aging, where weight assigned to a given classifier is inversely proportional to its accuracy. 3. w1a1 -an ensemble using weighted voting with aging, where weight assigned to a given classifier is calculated according to (3). Method of ensemble pruning was the same for each ensemble and presented in Alg.1. The only difference was line 19 of the pseudocode what was previously described. All experiments were carried out in the Java environment using Weka classifiers [START_REF] Hall | The weka data mining software: an update[END_REF].

Results

The results of experiment are presented in Fig. 12. The first figure shows the accuracies of the tested ensembles for a chosen experiment. Unfortunately, because of the space limit we are not able to presents all extensive results, but they are available on demand. Fig. 2 presents overall accuracy and standard deviation for the tested methods and how they depend on data chunk size. On the basis of presented results we can formulate several observations. It does not surprise us that quality improvements for all tested method according to increasing data chunk size. Usually the WAE outperformed others, but the differences are quite small and only in the case of ensemble built on the basis of Naive Bayes classifiers the differences are statistical significant (t-test) [START_REF] Alpaydin | Introduction to Machine Learning, Second Edition[END_REF] i.e., differences among different chunk sizes. The observation is useful because the bigger size of data chunk means that effort dedicated to building new models is smaller because they are being built rarely. Another interesting observation is that the standard deviation is smaller for bigger data chunk and usually standard deviation of WAE is smallest among all tested methods. It means that the concept drift appearances have the weakest impact on the WAE accuracy.

Conclusions

We discussed the ensemble classifier approach applied to data stream classification task. We showed an idea and performance of WAE algorithm, which uses dynamic classifier ensemble i.e., its line-up is formed when new data chunk is come and the decision which classifier is chosen to the ensemble is made on the basis of General Diversity (diversity measure). The decision about object's label is made according to weighted voting where weight assigned to a given classifier depends on its accuracy (proportional) and how long the classifier participates in the ensemble (inversely proportional). It is worth noting that classifier ensemble is a promising research direction for aforementioned problem. Maybe its combination with a drift detection algorithm could have a higher impact to the classification performance.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Classification accuracy of the ensembles consist of Naive Bayes classifiers for the chunk size = 200. Vertical dotted lines indicate concept drift appearances.

Acknowledgment

The work was supported by the Polish National Science Center under a grant N N519 650440 for the period 2011-2014.


Kateřina Slaninová
email: slaninova@opf.slu.cz

Jan Martinovič
email: jan.martinovic@vsb.cz

Roman Šperka
email: sperka@opf.slu.cz

Pavla Dráždilová
email: pavla.drazdilova@vsb.cz

Extraction of Agent Groups with Similar Behaviour Based on Agent Profiles

Keywords: Agent Profile, Log Analysis, Agent Behaviour

This paper deals with the log files suitable to extract valuable information about agents and their behaviour from agent-based simulation in a model of virtual company. Such information, presented in a transparent way, can be used as a support for simulation verification to achieve the suitable design of the proposed system. Hence, based on the similar behaviour (represented by extracted sequences) of agents, we are able to construct models which explain certain aspects of agent behaviour. Moreover, we can extract agent profiles based on behaviour and find latent ties between different agent groups with similar behaviours. The paper extends the results of our previous works about sequence extraction and comparison. The approach for agent network construction based on agent profiles is described. Two different methods were used for construction of agent network. One method uses cosine similarity and graph partitioning and the second self organization maps and Euclidean similarity for agent relations. Each of these methods has its advantages and disadvantages which are summarized in the paper and presented in the form of the visualization of relations between agents.

Introduction

Modern applications like information systems, enterprise systems or e-commerce systems, as well as monitoring applications, web applications, and other systems produce a large amount of data collections. These data collections are usually kept in databases, data warehouses, or simply in data or log files.

A standard log file typically consists of records with information about recorded events that have occurred in the system. These records may contain various attributes such as information about the date and time when the event happened, an originator, the type of event and additional information. The originator can be a person, a device, or software. This depends on the type of log file. In the case of a person, we can extract the relevant records and obtain information about his behaviour. This paper deals with the log files suitable to extract valuable information about agents and their behaviour from agent-based simulation in a model of virtual company [START_REF] Barnett | Modeling & simulation in business process management[END_REF]. The motivation to use agents as simulation subjects outcomes from the agents characteristics e.g. autonomy, coordination, communication etc. precisely declared in [START_REF] Wooldridge | An Introduction to MultiAgent Systems[END_REF][START_REF] Macal | Tutorial on agent-based modeling and simulation[END_REF]. This ensures to substitute real business processes participants (sellers and customers) and simulate their trading communication. Such information, presented in a transparent way, can be used as support for simulation verication to achieve the suitable design of the proposed system.

This paper is focused on log files where one log file attribute is an originator of the recorded activity, and the originator is an agent. Hence, based on the similar attributes of agents, we are able to construct models which explain certain aspects of an agent behaviour [START_REF] Van Der Aalst | Discovering social networks from event logs[END_REF]. Moreover, we can extract agent profiles based on behaviour and find latent ties between different agent groups with similar behaviours.

Log Analysis

Log analysis is a data mining process focused on the analysis of computer-generated records (also called audit trail records, event logs or transaction logs) [START_REF] Van Der Aalst | Workflow mining: a survey of issues and approaches[END_REF]. Log file analysis has gained growing attention in all areas of human activity. This domain is very interesting not only for researchers, but for commercial software developers as well. There are various disciplines considered in the analysing of data sources with the intention of achieving worthy information, often represented as knowledge. Obtained information (or knowledge) is then used for management, system maintenance, and system optimisation, marketing campaigns, recommender systems or other purposes such as discovering a company's structure or the structure of social networks.

A log file is usually a simple text file generated by a device, software, application or system. It consists of messages, which are represented by records of events performed in the system. An event log consists of cases, whilst cases consist of events. It typically contains activity information in events, but mostly timestamp, originator (performer) and other necessary data as well.

In a case, the events are represented in the form of a trace, i.e. a sequence of unique events [START_REF] Van Der Aalst | Discovering social networks from event logs[END_REF][START_REF] Van Der Aalst | Process Mining: Discovery, Conformance and Enhancement of Business Processes[END_REF]. If an event log contains timestamps (a time when the event was performed in the system) then the ordering in a trace respects this attribute # time (e).

Pattern Mining

Unsupervised pattern mining is used for pattern recognition tasks, where training feature vectors with known class labels are not available. In this type of problem, there is used a set of feature vectors x, and the main goal is to achieve clusters (groups) of vectors on the basis of their similarity (or proximity measure). This process is generally known as clustering.

In the experiments, selected pattern mining methods were used to find patterns of similar behaviour of agents and to find groups of agents with similar behaviour. This section is only short introduction of the selected methods, used in the case study.

Self Organizing Maps

Self organizing maps (SOM), also called Kohonen maps, is a type of artificial neural network invented by professor Teuvo Kohonen in 1982 [START_REF] Kohonen | Self-Organization and Associative Memory[END_REF]. The input space of the training samples is represented in a low dimensional (often two-dimensional) space, called map. The model is capable of projecting a high-dimensional space to a lowerdimensional space and is efficient in structure visualization due to its feature of topological preservation using a neighbourhood function. Obtained low-dimensional map is often used for pattern detection, clustering, or for characterization and analysis of the input space [START_REF] Vojáček | Combined method for effective clustering based on parallel som and spectral clustering[END_REF]. The Euclidean distance is used in the SOM algorithm.

Spectral Clustering

Spectral clustering is one of the divisive clustering algorithms which can be applied in the graph theory. The spectral clustering algorithm uses eigenvalues and eigenvectors of a similarity matrix derived from the data set to find the clusters. In this section, there is described the type of spectral clustering based on the second smallest eigenvector of the Laplacian matrix.

How to use the spectral algorithm is studied in [START_REF] Kannan | On clusterings: Good, bad and spectral[END_REF] by Cheng et al. In [START_REF] Ding | A min-max cut algorithm for graph partitioning and data clustering[END_REF] Ding et al. proposed a new graph partition method based on the min-max clustering principle: the similarity between two subgraphs (cut set) is minimized, while the similarity within each subgraph (summation of similarity between all pairs of nodes within a subgraph) is maximized.

Spectral clustering method optimized by our proposed Left-Right Oscillate algorithm [START_REF] Dráždilová | Spectral clustering: Left-right-oscillate algorithm for detecting communities[END_REF] was used in two parts of the proposed approach: for finding the behavioural patterns and for better visualization of agent network based on their similar behaviour in the system.

Business processed and Agent-Based Simulation

The main motivation for the research in the field of business process simulation was to investigate agent' behavioural patterns and to find groups of agents with similar behaviour during the agent-based simulation in a model of virtual company. Used multiagent system (MAS) operates with randomly (resp. pseudo randomly) generated parameters, and is able to deal with unpredictable phenomena surrounding the company. To achieve the suitable design of the proposed system, a mechanism for verification is needed.

Agent-based simulations dealing with a company simulation can bring several crucial advantages [START_REF] De Snoo | Modeling planning processes with talmod[END_REF][START_REF] Jennings | Autonomous agents for business process management[END_REF]. It is possible to involve unpredictable disturbance of the environment into the simulation with the agents. The analysis and visualization of agent behaviour lead to facilitate the verification of the simulation model and to effectively observe the reaction of the model in relation to the initialization of its input attributes, or in relation to the influence of the model environment.

Simulation Model

The agent-based simulation model from which were analysed data outputs is described in [START_REF] Macal | Tutorial on agent-based modeling and simulation[END_REF], with the focus on Business Process Management (BPM). Usual business process simulation approaches are based on the statistical calculation, as can be seen for example in [START_REF] Scheer | Aris architecture and reference models for business process management[END_REF]. However, only several problems can be identified while using the statistical methods. The model uses the advantages of the agent technology, to describe some of the core business processes of a typical business company. The authors in [START_REF] Spišák | Šperka Roman: Financial market simulation based on intelligent agents -case study[END_REF] developed a business process simulation framework in order to simulate the real behaviour of the company on the market.

The core of the experiments was the analysis of the agent-based simulation outputs. To ensure the outputs, above mentioned framework was used to trigger simulation experiments. The simulation framework covered business processes supporting the selling of goods by company sales representatives to the customers.

Each activity performed by agents in the simulation model was recorded into a log file. The log was a simple text file, where each row represented one event. The main row structure, which was valid for all agents, consisted of following event attributes: # time (e), denoted as TimeStamp (date and time when the event was performed), # resource (e), denoted as AgentID (each agent had its unique ID), # activity (e), denoted as TypeOfAction, and other additional attributes like AgentClassName or ActionAttribute. Example of the log file is presented in Example 1.

Example 1 (Example of Log File -Simulation Model

Proposed Approach with Case Study in Business Process Simulation

The proposed approach proceeds from the original social network approach with a modification focused on agent behaviour. The modification is based on a definition of the relation between agents. The original approach to the analysis of social networks deals with the assumption that the social network is a set of people (or groups of people) with social interactions among themselves [START_REF] Newman | Networks: An Introduction[END_REF]. Social interaction is commonly defined as interaction between the actors like communication, personal knowledge of each other, friendship, membership, etc... The modification extends the original approach of social network analysis by the perspective of the complex networks. This type of view differs from the original approach in the description of relations between the nodes (agents). The relation between the agents is defined by their common attributes characterizing their behaviour in the system. More specifically, the agent behaviour in the system is defined by agent profiles.

Creation of the agent profiles requires a set of agents U and a set of event sequences S performed in the system by the agents. Extraction of these sets is described in our article [START_REF] Slaninová | Analysis of agents' behavior in multiagent system[END_REF].

Definition 1. (Base agent profile, sequences)

Let U = {u 1 , u 2 , . . . , u n }, be a set of agents, where i = 1, 2, . . . , n is a number of agents u. Then, sequences of events σ i j = e i j1 , e i j2 , . . . e i jm j , are sequences of events executed by the agent u i in the system, where j = 1, 2, . . . , p i is a number of that sequences, and m j is a length of j-th sequence. Thus, a set S i = σ i1 , σ i2 , . . . σ ip i is a set of all sequences executed by the agent u i in the system, and p i is a number of that sequences.

Sequences σ i j extracted with relation to certain agent u i are mapped to set of sequences σ l ∈ S without this relation to agents: σ i j = e i j1 , e i j2 , . . . , e i jm j → σ l = e 1 , e 2 , . . . , e ml , where e i j1 = e 1 , e i j2 = e 2 , . . . , e i jm j = e ml .

Define matrix B ∈ N |U|×|S| where

B i j = f requency o f sequence σ j ∈ S f or agent u i if σ j ∈ S i 0 else
A base agent profile of the agent u i ∈ U is a vector b i ∈ N |S| represented by row i from matrix B. Example 2 shows an example of base agent profile generated for agent behaviour during a business process simulation in the multi-agent system.

Example 2 (Example of Base Agent Profiles).

#agent:sa0028 0|1|ability_generated;|0; 1|253|sent_proposal;sent_proposal;sent_proposal;sent_proposal; ... 3|1|sent_proposal;sold;|6;11;

Similarity between two profiles can be quantified by several methods. The selection of the method depends on the type of data used [START_REF] Deza | Dictionary of Distances[END_REF]. For Boolean data, Hamming distance, Jaccard dissimilarity or Rogers-Tanimoto dissimilarity may be used. In the case of numerical data, Euclidean distance, Manhattan distance, cosine similarity or correlation distance may be used. If we use string data, then Edit distance, Levenshtein distance or Hamming distance are all potential options. In this paper, the similarity between agent profiles was determined by using Euclidean similarity [START_REF] Elmore | Euclidean distance as a similarity metric for principal component analysis[END_REF] and cosine similarity.

Network of Agent Groups with Similar Behaviour

The network of agent groups with similar behaviour was created using graph theory approach. In this phase of the presented approach, it was constructed a weighted and undirected graph G(V, E), where vertices (graph nodes) V were agents u i and relations (edges) E expressed the similarity between the agent profiles.

The output graph can be obtained by comparison of Base agent profiles. The edge weights were counted by cosine similarity in this paper. As the output, we obtained a graph of agents (a .gdf file). Another output was a file with set of agents U and their vectors consisted of sequences (behavioural patterns) and their frequency. In this last phase of the proposed approach, two methods for construction of network of groups with agents were compared. The first method proceeded from graph of agents, mentioned before. The groups of agents with similar behaviour (similar agent profiles) were found using spectral clustering by Fiedler vector using Left-Right Oscillate algorithm. The graph was constructed only from edges, which weight was higher than a selected threshold. The graph contained the isolated agents (nodes) as well, because they are as important as the other connected nodes. They created a separate component in the graph, see example graph of groups of agents with similar behaviour in multi-agent system in Figure 1.

The second method used for the construction of agent network with groups of agents with similar behaviour was SOM. This method used a file with agents and their vectors consisted of sequences (behavioural patterns) and their frequency as the input for SOM.

The goal of this method was to obtain such output SOM map, where each neuron of the output map consisted of agents with similar behaviour (with similar agent profiles). However, the output SOM map has its predefined structure (in our case lattice), which is not suitable for visualisation of agent network. In Figure 2, we can see example Therefore, we have used further steps to transform SOM output lattice to graph of groups with agents. This transformation was performed by removing the empty neurons (neurons to which none of agents were assigned). The rest of nodes from output SOM lattice were considered as graph nodes with groups of agents. Due to information about the distance between the neurons, we obtained the weights for relations between the nodes (Euclidean similarity). It is common that some neurons may be very close, which means that the agents in such neurons may be very similar, and may create one group in the agent network. Therefore, a further clustering and colouring of the obtained clusters in a graph of agents was performed using spectral clustering method by Fiedler vector and Left-Right Oscillate algorithm. The different colours represent clusters of agents with similar behaviour.

Moreover, the graph of agents can be reduced into a graph of agent clusters, where clusters contain agents with similar profiles. This approach is suitable for better visualization in cases with large amounts of agents, see example in Figure 4.

Conclusion and Future Work

In the paper, the approach which uses agent profiles for finding of agents groups with similar behaviour have been introduced. This approach may use different methods for groups construction. As founded during presented experiments, each method has its advantages and disadvantages. In the last section, there was presented cosine similarity and graph partitioning method as one possible way for this purpose. Another presented way was based on SOM and graph extraction from SOM output which uses Euclidean similarity.

The results showed, that if we use cosine similarity, the agent without any identical sequences will be in different clusters (groups of agents). The Figure 2 presented results of the tested simulation where two big and compact clusters were found. The problem of this method was, that it was not able to detect tiny changes in the frequency of sequences in agent profiles. Therefore, the agent clustering based on their similar behaviour was too rough.

To remove this disadvantage, SOM method was used, and the SOM output map was transformed to the graph. Such approach resolved the problem with detection of tiny changes between agents behaviour. However, this representation had a problem that the relation between totally different profiles could be constructed. This was caused by the reduction to lower dimensions represented by SOM map.

The both disadvantages described above could be resolved by combination of the obtained results. We intent to work on splitting the agents without common sequences in the graph obtained from SOM map. For this purpose, we will use clusters obtained by cosine similarity and graph partitioning.

Fig. 1 .

 1 Fig. 1. Example of Agent Network (Spectral Clustering and LRO)

Fig. 2 .

 2 Fig. 2. Example of Clusters with Agents Visualized by SOM

Fig. 3 .

 3 Fig. 3. Example of Agent Network (SOM)

Fig. 4 .

 4 Fig. 4. Example of Reduced Agent Network (SOM)

  ).

	2012/03/26 01:14:14 : SA0022 bpm.selling.SellerAgent SENT_PROPOSAL CA0223,12,5.0006104,73
	2012/03/26 01:14:14 : SA0008 bpm.selling.SellerAgent SENT_PROPOSAL CA0088,8,5.0097656,31
	...
	2012/03/26 01:14:15 : CA0183 bpm.selling.CustomerAgent RECEIVED_CPF_MESSAGE SA0018,8,5.004883,53
	2012/03/26 01:14:15 : CA0170 bpm.selling.CustomerAgent SENT_REPLY SA0017,false,1.0462701894732744,5.0006104,29
	2012/03/26 01:14:15 : CA0170 bpm.selling.CustomerAgent FINISHED_TURN
	In used multi-agent model, there were monitored five types of agents: SellerAgent,
	CustomerAgent, ManagerAgent, InformativeAgent and DisturbanceAgent.

Acknowledgments. This work was partially supported by the grant of Silesian University in Opava, Czech Republic, No. SGS/06/2013 'Advanced Modeling and Simulation of Economic Systems' and by SGS, VSB -Technical University of Ostrava, Czech Republic, under the grant No. SP2013/167 'Analysis of the behaviour patterns in complex networks'.