extfieldsofstudy:
Engineering
Computer Science
Medicine

s2fieldsofstudy:
Computer Science
Business

text:
An Efficient Management System for Wireless Sensor Networks

Wireless sensor networks have garnered considerable attention recently. Networks typically have many sensor nodes, and are used in commercial, medical, scientific, and military applications for sensing and monitoring the physical world. Many researchers have attempted to improve wireless sensor network management efficiency. A Simple Network Management Protocol (SNMP)-based sensor network management system was developed that is a convenient and effective way for managers to monitor and control sensor network operations. This paper proposes a novel WSNManagement system that can show the connections stated of relationships among sensor nodes and can be used for monitoring, collecting, and analyzing information obtained by wireless sensor networks. The proposed network management system uses collected information for system configuration. The function of performance analysis facilitates convenient management of sensors. Experimental results show that the proposed method enhances the alive rate of an overall sensor node system, reduces the packet lost rate by roughly 5%, and reduces delay time by roughly 0.2 seconds. Performance analysis demonstrates that the proposed system is effective for wireless sensor network management.

Introduction
Wireless sensor networks have garnered considerable attention recently. The ability of sensor networks to sense, communicate and process data has led to the rapid development of such networks. Many researchers have attempted to improve wireless sensor network management efficiency. Wireless sensors networks can sense and monitor information from the physical world, and are used in the scientific, medical, and commercial domains. Sensor nodes can operate autonomously to collect and exchange information in a particular environment [1]. Wireless sensor networks with large nodes will acquire very large amounts of data. Network management then becomes very difficult. Supporting convenient and effective network management is crucial in wireless sensor networks. This paper intends to improved network configuration, performance, and fault management using WSNManagement, a novel management system for wireless sensor networks [2,3].
The Simple Network Management Protocol (SNMP) provides good management capability for TCP/IP-based networks and it is the most widely used network management tool. SNMP is an application layer protocol that promotes the exchange of information between network devices. It allows network administrators to manage network performance, identify network problems, and enhance network performance. SNMP is widely supported by the vendor community, and has been successfully used to manage both wired and wireless networks. We utilized the SNMP-based functions to manage wireless sensor networks.
The remainder of this paper is organized as follows. Section 2 reviews work on sensor management problems. Section 3 describes the proposed WSNManagement system in detail. Section 4 presents the simulation environment, and implementation and analysis results. Section 5 presents the performance of the WSNManagement system. Conclusions are given in Section 6.

Simple Network Management Protocol (SNMP)
SNMP is based on the manager and agent model, which consists of a manager, agent, and management information database [4]. The manager model provides an interface between a human manager and a management system. The agent model provides an interface between the manager and the physical device being managed ( Figure 1). The manager and agent use management information and a relatively small set of commands to exchange information [5].

Wireless Sensor Network
Wireless sensor networks combine the capabilities of low-power processors and wireless communication modules for particular services. Cheap, portable, low-power, tiny multifunctional sensor nodes have recently been developed for wireless communication and digital electronic devices [6].
The two most important tasks for a sensor node are information collection and transferring data traffic. Information gathering encompasses environment sensing and information processing. Traffic transmission may transfer original sensing data or forward traffic as in an intermediate relay in a multi-hop path. Sensor nodes can be either distributed as a mass or one by one in a sensor field. Once deployed, sensor nodes start working and may auto-organize, wait for a command to work, or start sensing and forwarding data. Sensor nodes usually relay a data stream to a base station or command node (management node) based on a regular rule or event.
Sensor nodes in wireless sensor networks are spread over a region and communicate using point-to-point wireless communication. Sensor nodes collect, process, and send data obtained from an environment. Wireless sensor networks can use three different nodes.  Common node: This node collects environment information and then sends data to a sink node.  Sink node: This node receives data from sensor nodes and may store, process, or compress the data.  Manager node: This function displays data for manager analysis. It also allows a manager to query sensor nodes. A manager node is connected to a sink node directly via a wireless connection or through another communication channel. Figure 2 shows these manager nodes and the communication method.

Sensor Network Management Functions
The objective of wireless sensor networks is to monitor and control a physical environment and achieve specific goals. Wireless sensor networks are designed to promote productivity when combined with the functions of an organizational of configuration, operation, management, and maintenance services in sensor networks [7].
A MANNA (Management Architecture for Wireless Sensor Network) architecture was proposed in Reference [8]. The functions of a wireless sensor network differ from those of a traditional network. In the MANNA architecture, the fault, security, performance, and accounting functions are dependent on configuration management.
Configuration management is a high correlation of sensor nodes in wireless sensor network management system. The goal of WSNManagement is to monitor sensor network collection, processing, and transmission of data, and ultimately control an environment. Problems or unexpected situations may adversely affect the configuration of services provided. Functions of management have been identified configuration of network-level requirements, which is the network operating environment, monitoring the environment, and node deployment.
As failures can occur in a wireless sensor network, wireless sensor network management differs from traditional network management. Sensor failure can be due to energy shortages, connection interruptions, and environmental changes. Thus, a sensor network must be robust, and must function even when individual nodes, networks, or even services fail. In addition to problems caused by energy issues, other problems can occur in wireless sensor networks, such as those associated with communications, services, data processing, physical equipment failure, operator violation, or security non-safety.
Providing wireless sensor network security features is difficult because of their ad hoc features, intermittent connections, and wireless communication and resource constraints. Furthermore, wireless sensor networks are subject to internal, external, accidental, and malicious security threats. Information or resources can be modified, stolen, deleted, or lost, and service can be interrupted. Even when a wireless sensor network is secure, the network environment can be unsafe or vulnerable [9][10][11][12].
The two main objectives for performance management of a WSN are acquisition of quality information and distribution of services. A trade-off exists in performance management among the highest number of managed parameters, the highest energy consumption, and lowest network lifetime. Conversely, when parameter values are not obtained, managing a network appropriately is impossible.

WSNManagement Architecture
Wireless sensor networks are applied in many fields. As network type and structure are versatile in complex network environments, a network manager must be able to control and understand information and the operating situation to ensure that network resources are used efficiently. However, these goals are not achievable when done by a human. Therefore, a network manager must work with network management systems to integrate monitoring tasks and control network traffic. An effective network management system must provide the following functions to assist network managers.
(1) A network management system must automatically search and display network ability and its connection on the Graphical User Interface (GUI). The system must also provide a network operator with a thorough understanding of the network environment, such that the operator can monitor and control remote devices.
(2) A network management system must collect data and assess network utilization, and make adjustments according to analytical results.
(3) When an abnormal network situation occurs, the system must automatically notify management staff, identify the probable cause, and provide a solution.
The structure and functionality of the WSNManagement network management system is presented in this section. How a network manager manages a sensor network with the WSNManagement system is also described.

WSNManagement System Architecture
The network manager can use an easy operation environment to monitor and examine a network system. The WSNManagement system can manage all abilities on a sensor, and control communication, configuration, and backup support for a network management system. These are practical issues and crucial to network management. Furthermore, diagnosing situations by statistical analysis of different network applications and forecasting trends are important to future network adjustments.
Network administrators use the Configuration, Performance, and Fault functions of the WSNManagement user interface to obtain values from a sensor node through the Communication technology and TOSSIM [12] or mote according to Commands and Events provided by the Event-Bus.
The Command signal is sent by the WSNManagement user interface through the TOSSIM as an administrator command. Figure 3 shows the WSNManagement system architecture.

Configuration Management
Configuration management searches and sets sensor status in a sensor network to control and monitor the status of sensor nodes. The sink node is linked to each sensor node through the Communication function, which can determine network status. Network administrators can manage sensor networks via the GUI (e.g., redeploying, increasing, or decreasing the sensor node based on sensor node density). Configuration management is used to obtain data from sensor networks.

Performance Management
The purpose of performance and administration control is to keep a system operating, and to ensure secure data transmission. Performance and administration control can help an administrator monitor sensors, collect performance data, record detected values (e.g., temperature and luminosity) from sensors, and monitor power consumption. Via these data, an administrator can analyze and predict the development of an entire network, such that the administrator can solve problems or upgrade a system as soon as network performance declines.

Fault Management
Function of fault administrator control enhances network reliability. For network awareness, one must monitor network status. By analyzing historical data, consecutive events, or event queries from sensors, the fault administrator control process can obtain current data. Fault administrator control can be used to identify errors associated with sensor hardware faults, power shortages, lost connections, and environment changes.

WSNManagement System Implementation
The WSNManagement system is implemented with Java as a plug-in of TinyViz and connects to Tinyos [14] motes and TOSSIM through the TCP port. Figure 4 shows the user interface of the WSNManagement system. The WSNManagement system has a list of functions at the top of the window. A node display window is on the left and network management function selection tabs are on the right under the functions list.
The "file" function loads the location map of sensor nodes. The "layout" function can change the layout of sensor nodes to a grid or a randomly generated one. The "plugin" function is used to add user-defined plugins to the system. The "play" button is on the function list and represented by a triangular green arrow. When the "play" button is pressed, the simulation starts and the "play" button changes into a "pause" button (two vertical grey bars). Sliding the "delay" slide (center of the function list) slows the rate at which events are generated and processed from the simulation. The "grid" button (a grey grid) displays grid lines in the node display window. The "clear" button clears simulation information and displays sensor nodes.
They are generated randomly or deployed according to an input map in the locations of mote nodes. When simulation is in random mode, the WSNManagement system places motes in random locations in the node display window. Users can move any node and change its location in the entire sensing field; this triggers an event and changes the "real" location of motes in the TOSSIM. The wireless sensor network manager can perform management tasks and obtain useful information using the configuration, performance, and fault tabs in the network management tab. These special features include deployment, sensing coverage, system life and faulty sensor nodes. The sensor network management functions are described in detail in following sections.

Configuration Management
Sensor nodes in the experiments were deployed randomly. The sensor with the id 0 was chosen as the sink node. The sink node communicated with each node via broadcasting and collected data from each sensor node. Figure 5 shows the sensor node display window. By examining the sensor node display window, a network manager can analyze the deployment of sensor nodes. Additionally, the network manager can read the coordinates of sensors in each sensor node. Furthermore, the network manager can determine that no sensor node exists in the rectangular area and that the density of nodes in the circular area is excessive. In the simulation case, the network manager can adjust the locations of sensor nodes by dragging and grouping nodes to meet the requirement of the sensor network system. Figure 6 shows the new configuration after adjustments. In the case of mote nodes deployment, the network manager can remove mote nodes in the circular area and redeploy them in the rectangular area to increase distribution uniformity. When moving sensor nodes to a dangerous area is impossible, the network manager can deploy sensor nodes to areas that need additional sensors to meet system requirements. Figure 7 shows the outcome of altering sensor deployment in the sensor network. Hence, the network manager can manage the sensor network configuration.

Performance Management
Sensing coverage is an important metric of sensor network performance. During performance management, the performance tab displays sensing coverage of the current designated sensor in the sensor node in the WSNManagement system. Figure 8 shows the sensing coverage of the current sensor node deployment. We assume the range of each sensor node is 10 units. In a real case, each sensor node can have multiple sensors. After deployment, a network manager can examine the configuration to determine coverage. The other performance metric is prolonged system life. Because sensor nodes are battery powered, power is a limited resource for all sensor networks. By examining sensing coverage and identifying the areas in which sensor node coverage overlaps, network managers can deactivate redundant sensor nodes temporarily until other nodes run out of power.

Fault Management
Sensor nodes are easily broken, communication can be obstructed by buildings and trees, and sensor node power is limited. Dead sensor nodes, faults, must be monitored by network managers. When performing fault management, a network manager can select the fault tab, which displays dead sensor nodes in grey in the WSNManagement system. Figure 9 shows faulty sensor nodes in the current deployment. The network manager can assess the effect of these faulty nodes on the entire system and decide whether to deploy new nodes to keep the system functioning properly.  This work of WSNManagement system provided Communication, Event bus, and WSNView module, can be applied to the real networks to enhance management efficiency. This contributes a novel and original researches. In our proposed system, real wireless sensor network can be combined to obtain actual node information from the outside environment. Figure 10 shows the integrated WSNmanagement system.

Performance Analysis
This work proposed the WSNManagement system for performance analysis. Using this system, one can determine whether to use the configuration, performance, or fault management mechanisms for performance comparisons. The simulation environment was built for assessing the alive rate for nodes, the packet loss rate, and delay time for performance comparisons. The detailed parameter settings are as follows. The simulation environment contains a sink node and common node. The common node can identify environmental changes in temperature and humidity, and transmit these data back to the user. The simulation environment is close to reflect the real network environment to get performance result. The term with WSNmanagement means the environment using WSN management and the term without WSNmanagement means the environment not using WSN management.
 Alive means sensor nodes in the sensor network are alive.  The packet loss rate is the number of packets lost sent from the source minus the number of packets received at the destination.  The delay time is the average time required to send a packet from a source to the receiver. Figure 11 shows the node alive rate of the network. One can use the WSNManagement mechanism to enhance the number of alive nodes in a network. Figure 11. System Alive Rate. Figure 12 shows that the packet loss rate for data transmission with the WSNManagement mechanism is about 5% less than the one without WSNManagement mechanism. Simulation results demonstrate that the algorithm effectively enhances network data transmission services. These experimental results further indicate that transmission through the control network node can improve network traffic stability, reduce the packet loss rate, and increase the data arrival rate. Figure 12. System Packet Loss Rate.
The WSNManagement system has a shorter delay, which is 0.2 seconds shorter than sensor networks without the WSNManagement system ( Figure 13). The performance of the proposed framework for selecting the shortest network routing for WSNManagement data transfer is better than that without the WSNManagement system.

Conclusions
This work proposed a novel system that can show connection stated in wireless sensor networks relationships among sensor nodes and can monitor, collect, and analyze information from a wireless sensor network. This work of WSNManagement system provided Communication, Event bus, and WSNView module, can be applied to the real networks to enhance management efficiency. This contributes a novel and original researches. In our proposed system, real wireless sensor network can be combined to obtain actual node information from the outside environment. For the performance analysis demonstrates that the proposed enhances the alive rate, reduces the packet lost rate and delay time. The system interface and sensor network were examined in detail using the popular sensor network TinyOS mote and its simulation environment TOSSIM. The events and commands of TinyOS were described and categorized by the WSNManagement system. The special features of sensor network management, including deployment, sensing coverage, system life and faulty sensor nodes, were extracted and implemented in the WSNManagement system. The wireless sensor network management functions covered configuration, performance, and fault management for various situations.


extfieldsofstudy:
Medicine
Computer Science
Physics
Biology

text:
Link communities reveal multiscale complexity in networks.

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society. One crucial step when studying the structure and dynamics of networks is to identify communities: groups of related nodes that correspond to functional subunits such as protein complexes or social spheres. Communities in networks often overlap such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure. However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks, including major biological networks such as protein-protein interaction and metabolic networks, and show that a large social network contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society. [1][2][3] One crucial step when studying the structure and dynamics of networks is to identify communities; 4 groups of related nodes that correspond to functional subunits such as protein complexes [5][6][7] or social spheres. [8][9][10] Communities in networks often overlap 9, 10 such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess multi-scale, hierarchical organisation, where communities are recursively grouped into a hierarchical structure. 5,[11][12][13] However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organising principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organisation. We find biologically relevant link communities in protein-protein interaction 6,7,14 and metabolic networks 15 and show that a large social network 10,16 contains hierarchically organised, community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and multi-scale hierarchical organisation in networks to be two aspects of the same phenomenon.
Although no common definition has been agreed upon, it is widely accepted that a community should have more internal than external connections. 17 A popular measure of community quality, modularity, is defined by comparing the the number of connections within a community with the expected number of connections within the community under randomi-sation of the network. 18 However, these standard definitions of community structure break down when overlap is pervasive. In many real networks, nodes typically possess multiple roles. 6,7,9,10,14,15 Pervasive overlap in real networks is distinct from 'fuzzy' community overlap with relaxed interfaces, [19][20][21] because overlap can exist for each and every node (Fig. 1a,b). When overlap is pervasive, counterintuitively, each community has many more external than internal connections. This overlap creates another serious problem: a single dendrogram cannot fully encode the hierarchy, since this dendrogram assumes disjoint community structure and prohibits nodes from simultaneously belonging to multiple, overlapping groups ( Fig. 1a-c).
Although the discovery of hierarchy and community organisation has always been considered a problem of determining the correct membership(s) of each node, notice that, while nodes belong to multiple groups (individuals have families, coworkers and friends), links often exist for one dominant reason (two people are in the same family, work together or have common interests). Thus, in contrast to nodes, link membership typically is uniquely defined, even when nodes belong to multiple, diverse communities. Instead of assuming that a community is a set of nodes with many links between them, we consider a community to be a set of links that are densely interconnected. Each link is defined in a single context, allowing for a unique hierarchical tree (where each leaf is a link from the original network) to be constructed (see Methods). The result is a dendrogram whose branches represent link communities. In this dendrogram, links occupy unique positions and nodes naturally occupy multiple positions, due to their links. Agglomerating links leads to a dendrogram containing clearer and richer information than those of traditional methods. Extracting communities by cutting this dendrogram at various thresholds reveals the overlapping communities at multiple levels.
By clustering links we can now formulate overlapping community discovery as a well-posed optimisation problem, embracing overlap at every node without penalising that nodes participate in multiple communities. For this purpose, we in- troduce a natural objective function, the partition density D, based on the link density (see Methods). Computing D at each level of the link dendrogram allows us to pick the best level to cut, though structure exists above and below that threshold (Fig.  2); one can also optimise D directly.
To investigate multi-scale structural complexity in real networks, we study link communities in a social network derived from the anonymised billing records of a mobile phone company (with a total of 8 million subscribers), representing the call patterns and locations of each user. 10,16,22 We generated a network of reciprocal calls between the users who make at least one call during a 30-week period within a particular 350 km by 80 km region which contains several large cities (Fig. 2a). We partition the link dendrogram at the threshold with maximum partition density (see also Fig. 4a). The three largest communities, at this optimum, are spatially correlated in the regions surrounding a major city (Fig. 2b). By partitioning the dendro-gram above and below the optimum, we uncover larger, regionspanning groups and smaller, intra-city communities, respectively. Specifically, as we approach the root of the dendrogram, we see large, spatially extended communities (Fig. 2c). Near the leaves, however, we find smaller, tightly clustered groups located inside densely populated regions (Fig. 2c). In Fig. 2e, we plot the network topology of the largest community from Fig. 2c, showing the multi-scale complexity of the underlying social group. Finally, Fig. 2f shows the highly overlapping structure in the largest sub-community. The dendrogram for this subgroup explicitly shows significant hierarchical structure alongside pervasive overlap. Additional validation of the discovered structure is presented in the Supplementary Information (SI).
We analyse recently published protein-protein interaction (PPI) networks of Saccharomyces cerevisiae, compiled into three genome-scale networks: 14 yeast two-hybrid (Y2H), affinity purification followed by mass spectrometry (AP/MS), and literature curated (LC). We also study the metabolic network reconstruction of E. coli K-12 MG1655 strain (iAF1260), one of the most elaborate reconstructions currently available. 15 We contrast link-and node communities (see Methods) on this test set, which covers networks from sparse (Y2H, k ∼ 3) to dense (E. coli, k ∼ 17), and from networks that are highly modular (AP/MS, LC) to networks with no visually apparent modular structure (E. coli). Figure 3 shows that, based on GOterms and pathway annotations, link communities have more biological relevance, across all types of networks. Several specific example communities, as well as lists of all discovered communities with their most enriched annotations, are contained in the SI and Supplementary Table 1,2.
Detailed statistics for the metabolic and phone networks are presented in Fig. 4a which contains coverage, the ratio of second largest to largest community sizes s 2 /s 1 , and partition density D, as a function of the clustering threshold. The community size distribution at the optimum D is heavy tailed for both networks (Fig. 4b). The number of communities per node distinguishes the two networks ( Fig. 4b insets): We can identify currency metabolites (water, ATP, etc.) by the high number of communities they participate in. Meanwhile, mobile phone users are limited to a smaller range of community memberships, most likely due to social and time constraints.
In summary, we have studied hierarchical organisation in the presence of pervasive community overlap. To incorporate both overlap and hierarchy, we developed a general approach based on hierarchical link communities. In most networks, it is a realistic assumption that links, rather than nodes, are characterised by a single attribute, such as community assignment. From this simple initial assumption we have resolved a major conflict in complex network research: how to combine community overlap with hierarchical structure. Many current techniques for analysing network structure, 12, 13 identify hierarchical structures well, but are unable to correctly analyse networks with pervasive community overlap. One community detection method, clique percolation, 9 successfully accounts for strong overlap, but suffers from problems due to sparsity and is unable to describe the large-scale hierarchical structure of real networks. Link communities incorporate both aspects simultaneously and stands out when compared to node clustering. Our link-centric viewpoint addresses the long-standing question of formulating overlapping community detection as an optimisation problem by introducing a new objective function, the partition density. Not only are strong overlap and hierarchical organisation not mutually exclusive, real networks possess both elements simultaneously.

Methods
Link similarity measure Define the inclusive neighbours n + (i) as the neighbours of node i, and node i itself. Lim-iting ourselves to link pairs that share a node, which are expected to be more similar than disconnected link pairs, the similarity S between links e ik and e jk , sharing node k can now be given by, e.g., the Jaccard index: The shared node k does not appear in S because it provides no additional information and introduces bias. The SI contains a detailed discussion of this measure as well as generalisations to multipartite and weighted graphs.
Hierarchical clustering Each link is initially assigned to its own community; then, at each step, the pair of links with  14 and coverage, the fraction of nodes placed into communities (see Methods). Link clustering consistently finds more relevant communities than node clustering in all of these networks. (b) An example from the compendium PPI network of S. cerevisiae, showing the communities around protein TRA1, illustrating the importance of overlap and the rich information contained within link communities. Node clustering groups the distinct functional complexes of TRA1 into a single community while link clustering correctly identifies complexes. (c) Similarly, we show the E. coli metabolic network (iAF1260), which lacks observable global modular structure, in contrast to the networks used in previous studies, 11, 23 along with pathway enrichment and coverage. In this denser network, with more pervasive overlap, link clustering outperforms node clustering at both enrichment and coverage. See SI for details regarding measures, algorithms, and more examples.
the largest similarity is chosen and their respective communities are merged (single-linkage). Ties are agglomerated simultaneously. This process is repeated until all links have been agglomerated into a single cluster.
Partition density For a network with M total links and N total nodes, define P = {P 1 , . . . , P C } as a partition of its links into C subsets. The number of links in subset c is m c = |P c |. The number of induced nodes, all nodes that those links touch, is n c = ∪ eij ∈Pc {i, j} . Note that c m c = M and c n c ≥ N (assuming no unconnected nodes). We define the link density D c of subset c as In other words, this quantity is the number of links in community c, normalised by the minimum and maximum number of links possible between those same nodes, assuming they remain connected. We now define the partition density D as the average of D c over all communities, weighted by the fraction of links present in each: .
Node communities As with link similarity, similarity between node i and j can be defined as Fig. 3) are generated using the same singlelinkage hierarchical clustering; the node dendrogram is cut at maximum modularity. 18 This approach is closely related to the method used in Ravasz et al. 11 This method was chosen to be as similar to link clustering as possible in order to be a fair control.
Enrichment and coverage To compare sensitivity, we introduce a coverage measure, defined as the fraction of nodes that belong to at least one community of three or more nodes, which is the smallest size for a non-trivial grouping of nodes. To test specificity, we use functional similarity for proteins, and pathway similarity for metabolites (see SI for details). (a) Coverage, the ratio of the number of edges in the two largest communities, and the partition density D, respectively. The denser metabolic network requires a higher threshold to separate compared to the mobile phone data. In both networks, peaks in D correspond to s 2 /s 1 nearing 1/2, a possible transition point. 24 (b) The distribution of community sizes and node memberships (insets). Currency metabolites, such as water, belong to many communities, as expected. See SI for protein-protein interaction networks.

Supplementary Information
Link Communities Reveal Multi-Scale Complexity in Networks by Yong-Yeol Ahn, James P. Bagrow, Sune Lehmann

S1 Network Datasets
Here we discuss the biological and social datasets used throughout this work.

S1.1 Biological networks
We analyzed the protein-protein interaction (PPI) network of Saccharomyces cerevisiae and the metabolic network of Eschericia coli. We use a recently published dataset of PPI networks compiled into three genome-scale networks: yeast two-hybrid (Y2H), affinity purification followed by mass spectrometry (AP/MS), and literature curated (LC). 14 Various statistics for the PPI networks are shown in Fig. S5. To validate the biological relevance of the communities discovered by Hierarchical link clustering (HLC), in Sec. S1.1.2 we compile these three network into a compendium of protein interactions; otherwise the three networks are kept separate.
We also use a metabolic network reconstruction of E. coli K-12 MG1655 strain (iAF1260), one of the most elaborate metabolic network reconstructions currently available. 15 From this reconstruction, we retain only cellular reactions, ignore information regarding the compartments (cytoplasm and periplasm), and project the network into metabolite space (two metabolites are connected if they share a reaction). For instance, if an enzyme catalyzes the metabolites A and B into C and D, the resulting network would contain a clique of A, B, C, and D.
This set of biological networks covers a wide range of network topologies, from sparse (Y2H, k ∼ 3) to dense (the metabolic network of E. coli, k ∼ 17), and from networks that are highly modular (AP/MS, LC) to networks with no visually apparent modular structure (E. coli). These networks are shown in Figs. 3A-C and 3E of the main text.

S1.1.1 Global statistics
To compare each community detection method's sensitivity, we use a coverage measure, defined as the fraction of nodes that belong to at least one community with three or more nodes. This size threshold is introduced since clique percolation (CPM) can only find communities of size three or more, by definition. (HLC and most modularity-based methods assign every node/edge into at least one community.) In order to test specificity, we use a functional similarity measure for proteins, and a pathway similarity measure for metabolites: Proteins We adopt the same measure as the paper that published the datasets. 14 The enrichment of functionally similar pairs of proteins for a community c is defined by Ncs Nc / Nas Na , where N c is the number of possible pairs of proteins within the community boundary regardless of the existence of links between them, N cs is the number of functionally similar pairs among N c pairs based on their Gene Ontology (GO) Biological Process annotations , 26 N a = N (N − 1)/2 is the total number of possible pairs in the network, and N as is the number of functionally similar pairs among all N a pairs. Functional similarity is determined by the total ancestry measure with a p-value cutoff of 10 −3 . 27 Metabolites We use two measures for the metabolic network. The first is defined in the same sense as the PPI's functional enrichment measure, as J c /J a , where J a is the average Jaccard overlap of pathways between every pair of metabolites in the network and J c is the average Jaccard overlap between every possible pair of metabolites within community c. The Jaccard overlap between a pair of metabolites a, b is calculated by where N i represents the number of metabolites that have at least one pathway annotation in a community i, and N max i is the number of metabolites in the largest subset of community i which share the same pathway annotation.

S1.1.2 Biological relevance of detected communities
In analyzing each community's biological relevance, we use two networks: a single compendium of the Y2H, AP/MS, and LC datasets; and the metabolic network of E. coli. We evaluate the resulting communities using biological annotations. For the PPI network, we perform GO-term enrichment analysis to identify each community's biological role(s) or correspondence to existing protein complexes. For the metabolic network, we use the pathway annotation of each compound to identify the probable role(s) of each community in the metabolism. We use GO-TermFinder software 28 version 0.82 to find enriched GO terms and estimate the p-values for each GO term. First, we find all GO terms with p-value less than 0.05, then we pick up only the most significant term for each aspect (biological process, cellular component, molecular function). These terms and p-values are listed along with the community members in Supplementary  Table 1. This table shows that more than 80% of communities have at least one enriched GO-term with p-value lower than 0.0001 and more than 30% of communities have at least one enriched GO-term with p-value lower than 10 −10 .
For the metabolic network, we first filter out communities where less than three members possess pathway annotations. Then, we calculate the enriched pathway annotations shared by the largest number of community members. We compile this information in Supplementary Table 2. Fig. S6 shows the community structure around protein YML007W. There are three major communities, all three are related to the transcription process, identified as the mediator complex, NuA4 HAT complex, and SAGA complex, [29][30][31] respectively. Note the overlapping membership of protein YHR099W, which is already known as a subunit of both NuA4 complex and SAGA complex. [32][33][34] Figure S7 shows three major communities around the protein YBL041W, which belongs to the core of the proteasome complex. 35 We can directly observe that the proteasome consists of two parts: the core and the regulatory particles, and HLC finds two corresponding communities plus a community connecting the two. As expected from the structure of the proteasome, the core is less exposed to other communities, while the regulatory particles have several connected communities. Likewise, Fig. S8 shows the community structure around Acetyl-CoA, illustrating several roles that Acetyl-CoA plays in the metabolic network.

S1.2 Mobile phone network
This dataset catalogs approximately 8 million users, all calls among these users, and the locations of users when they initiate a phone call (the tower from which the call originated). Self-reported demographic information such as age and gender is also available for most users. We generate the network by constraining the location to a 350 km by 80 km region and two nodes in the region are connected only if they each call the other person at least once during a 30-week period. We assign to each user a single location, that of the tower they most frequently used. The final network contains approximately 600 thousand nodes and 2.8 million edges.
Applying HLC, the partition density and coverage, as a function of the threshold, are shown in Fig. S9. This shows that HLC achieves much better coverage than clique percolation at its preferred value of k = 4 . 36 As in biological networks, coverage is not the only important aspect of community detection. In the case of the mobile phone network, we can also use external information, the age and geographic location of the users, to qualify the accuracy of the discovered partition. First, we compute the age difference between pairs of nodes across the network and then for pairs within the same community. In a similar manner, we can look at the spatial "spread" of each community by making the assumption that each node is located at the cell tower it most frequently uses and computing the standard deviation σ in the distances between nodes in the same community. When compared to randomized communities we again find strong spatial clustering. See Fig. S10.   Figure S8: Overlapping community structure around Acetyl-CoA in the E. coli metabolic network. Acetyl-CoA plays several different and important roles in metabolism. Shown are only communities with homogeneity score equal to 1 (all compounds inside each community share at least one pathway annotation); all other links, including those that contribute to community structure, are omitted. Pathway annotations shared by all community members are displayed with corresponding colors. The two communities to the right of Acetyl-CoA are grouped since they share the same exact pathway annotations. The coverage (defined in Sec. S1.1) at maximum partition density for HLC compared to that of clique percolation. At the optimum threshold of 0.23, HLC achieves better coverage, more than twice that of clique percolation (the authors in 36 use k = 4 exclusively). Figure S10: Using demographic information to qualify communities in the mobile phone network. Note that HLC achieves twice the coverage of CPM. (Left) The age difference for random pairs of nodes chosen from the entire network and chosen from within discovered communities. An average age for new parents of ∼ 27 years is immediately evident from just cell phone records. (Right) A comparison of the geographic 'dispersion' of nodes inside communities. Shown is the standard deviation σ(s) of the geographic locations (most probable towers) of nodes within the same community, averaged over communities with the same number of nodes s versus σ rand (s) , the same quantity but from randomly chosen sets of nodes of size s. The plot confirms that both methods find significant, spatially correlated structure. CPM finds especially good structures, slightly outperforming HLC, albeit with much less coverage overall.
These results emphasize the point that CPM does well when detecting tightly knit communities. However, in the case of HLC, we are able to vary the clustering threshold to obtain fine-grained control, tuning for larger or smaller communities and observing hierarchical community structure spanning from the level of small communities consisting of only a few nodes, to large groups signifying much broader societal structures. For instance, Fig. 2 in the main text shows loosely connected large-scale communities (more than 500 people), which span the scale of cities (and are geographically distinct).

S1.3 Abundance of overlap
The abundance of overlap between communities is evident in social networks as pointed out in . 9 Intuitively this finding makes immediate sense: individuals belong to several distinct communities corresponding to friends, family, etc. The same concept also applies to biological networks. To underscore this point, Fig. S11 shows the distribution of functions per protein and pathways per metabolite. Although the number of functional categories and the number of pathways from databases does not directly correspond to the exact number of protein complexes or to that of metabolic pathways, it clearly shows that the overlap cannot be ignored in finding modules in biological systems. In the case of proteins, approximately two thirds of all proteins currently belong to more than one functional category. Although the metabolic network seems to exhibit less overlap than PPI, it is obvious that the currency metabolites such as water, proton, or ATP participate in a broad spectrum of pathways. According to the KEGG database, 37 the number of pathways assigned to water is only 5. However, HLC puts water into more than 200 communities (Fig. 4 in the main text), which correctly captures the abundant nature of currency metabolites . 38 Finally, the dense network shown in Fig. 1B is meant to be an illustration of the consequences of strong community overlap. However, it was constructed using an existing social network model, 39 which suggested that social networks can be modeled by probabilistically projecting a bipartite network that consists of people and communities.

S2.1.1 Constructing a dendrogram
The main text has introduced the HLC method to classify links into topologically related groups. Here we provide further motivation for the suggested pair-wise link similarity measure. For simplicity we limit ourselves to only connected pairs of links (i.e. sharing a node) since it is unlikely that a pair of disjoint links are more similar to each other than a pair of links that share a node; at the same time this choice is much more efficient. For a connected pair of links e ik and e jk , we call the shared node k a keystone node and i and j impost nodes.  If the only available information is the network topology, the most fundamental characteristic of a node is its neighbors. Since a link consists of two nodes, it is natural to use the neighbor information of the two nodes when we define a similarity between two links. However, since the links we are considering already share the keystone node, the neighbors of the keystone node provide no useful information. Moreover, if the keystone node is a hub, then the similarity is likely to be dominated by the keystone node's neighbors. For instance, if the hub's degree increases the similarity between the links connected to the hub also increases. This bias due to the keystone node's degree also prohibits us from applying traditional methods directly to the line graph of the original graph, which is constructed by mapping the links into nodes. (Since a hub of degree k becomes a fully connected subgraph of size k in the line graph, the community structure can become radically different.) Thus, we neglect the neighbors of the keystone. We first define the inclusive neighbors of a node i as: where d(i, x) is the length of the shortest path between nodes i and x. The set simply contains the node itself and its neighbors. From this, the similarity S between links can be given by, e.g., the Jaccard index: 40 S(e ik , e jk ) = |n + (i) ∩ n + (j)| |n + (i) ∪ n + (j)| (S5) An example illustration of this similarity measure is shown in Fig. S12 (See Sec. S3.1 for generalizations of the similarity).
With this similarity, we use single-linkage hierarchical clustering to find hierarchical community structures. We use single-linkage mainly due to simplicity and efficiency, which enables us to apply HLC to large-scale networks. However, it is also possible to use other options such as complete-linkage or average-linkage clustering. Each link is initially assigned to its own community; then, at each time step, the pair of links with the largest similarity are chosen and their respective communities are merged. Ties, which are common, are agglomerated simultaneously. This process is repeated until all links belong to a single cluster. The history of the clustering process is then stored in a dendrogram, which contains all the information of the hierarchical community organization.
The similarity value at which two clusters merge is considered as the strength of the merged community, and is encoded as the height of the relevant dendrogram branch to provide additional information.

S2.1.2 Partitioning the dendrogram
Hierarchical clustering methods repeatedly merge groups until all elements are members of a single cluster. This eventually forces highly disparate regions of the network into single clusters. To find meaningful communities rather than just the hierarchical organization pattern of communities, it is crucial to know where to partition the dendrogram. Modularity has been widely used for similar purposes in node-hierarchies, 18, 41 but is not easily defined for overlapping communities. 1 Thus, we introduced a new quantity, the partition density D, that measures the quality of a link partition. The partition density has a single global maximum along the dendrogram in almost all cases, because the value is just the average density at the top of the dendrogram (a single giant community with every link and node) and it is very small at the bottom of the dendrogram (most communities consists of a single link). This process is illustrated in Fig. S14.

S2.1.3 Link dendrograms and node hierarchy
A link dendrogram can be very different from a node dendrogram, see Fig. S13. As an (admittedly extreme) example, consider the graph shown in Fig. S15. Here we have constructed a simple network with two levels of hierarchy, consisting of four very dense communities, loosely connected into pairs which are then more loosely connected. At the lower level of the link dendrogram, we find six communities, not the expected four. The reason is that HLC has correctly identified the two sets of cross-community links.

S2.2 Node clustering
As a control, we compare HLC to a Hierarchical Node Clustering (HNC) method. The HNC method is used in Fig. 3 of the main text. HNC is closely related to the method introduced in Ravasz et al. 11 There are many ways to define a similarity between two nodes. We tried four different variations of the node similarity. The four versions are following: where n(i) means the neighbors, not inclusive neighbors, of the node i. Among those, we use the version in Eq. (S6) since it finds more relevant communities across most networks we used. In addition, it is the definition most similar to link similarity. Thus, the node similarity is chosen to be where, as in the main text, n + (i) are the inclusive neighbors of node i. To determine the node dendrogram, we use the same single linkage hierarchical clustering as we used for clustering links. This node dendrogram is cut at the point of maximum modularity. 18

S2.3 Other methods
In order to evaluate its performance, we have compared HLC to existing, popular community detection methods. We chose two representative algorithms: the Clique Percolation Method (CPM) 9 and a modularity-based agglomerative clustering algorithm. 45 We apply all three frameworks (HLC, CPM and modularity) to the biological networks studied in Fig. 3 of the main text, PPI (Y2H, AP/MS, LC) and the E. Coli. metabolic network. The results are displayed in Fig. S16. The modularity method 45,46 by definition identifies the membership of all nodes, but, as a consequence, the resulting communities are the least relevant in most cases. These results also highlight limitations of CPM's more rigid community definition. In the metabolic network, CPM's coverage is largely due to one giant community containing most nodes, leading to a miniscule enrichment value. Removing the giant community increases the enrichment value to close to 8, but only 12 small communities (∼ 5% of nodes) remain. This situation is hardly changed by increasing clique size. For Y2H, however, the problem is sparsity: there are not enough cliques to find structure. When the network is too dense, the network becomes super-critical in the sense of clique percolation and leads to giant clique communities. In contrast, when the network is too sparse, the network is sub-critical and there are not enough connected cliques to find.

Node Dendrogram (HRG)
Link Dendrogram (HLC) Figure S13: Comparison of a node dendrogram and link dendrogram in the presence of overlap. The node dendrogram is obtained by using the HRG method (consensus dendrogram) , 13 and the link dendrogram is obtained from HLC. Nodes are colored to distinguish each node or clique and dotted lines represent several hierarchies in the dendrogram. In the link dendrogram, two colored circles at each leaf represent the link between the nodes with the given colors. Note that HRG scatters the red, orange, and gray nodes in the dendrogram, even though they belong to the same clique. One cannot retrieve the clique community that consists of red, orange, and gray nodes. In contrast, the link dendrogram captures every clique while at the same time constructing a reasonable hierarchical tree. Note that the links of the red node are placed in appropriate branches of the dendrogram according to their context. Also note the internal hierarchical structures found inside each clique. Finally, real networks possess significantly more overlap than this example.  The chosen values of p i lead to a very "stretched" dendrogram and partition density, as expected. While one expects to identify four communities at the higher threshold, six are actually found, since the inter-community edges are identified by HLC.

S2.3.1 Modularity optimization
Although the particular modularity algorithm used here is the most popular one, more accurate methods exist, based on simulated annealing, extremal optimization, and more. (See 41 for additional details.) However, the modularity values we found are quite high, so the lack of accuracy in our comparison is more likely due to neglecting overlap rather than failing to find good partitions. The particular values found for the four biological networks are shown in Table S1. Note that visibly modular networks such as AP/MS and LC show high modularity values.

S2.3.2 Hierarchy and overlap
Several prominent methods for finding hierarchical organization exist, 12, 13 however, none are able to handle overlap since hierarchical structure always assumes disjoint community partition. In summary: CPM handles overlap, HRG handles hierarchy, but Hierarchical Link Clustering handles both. To further compare and contrast the three methods, see Fig. S17.

S3 Generalizations and Extensions
S3.1 Networks with weighted, directed, or signed links The similarity between links can be easily extended to networks with weighted, directed, or signed links (without self-loops), since the Jaccard index generalizes to the Tanimoto coefficient. 48 Consider a vector a i = A i1 , . . . , A iN with where w ij is the weight on edge e ij , n(i) = {j|w ij > 0} is the set of all neighbors of node i, k i = |n(i)|, and δ ij = 1 if i = j and zero otherwise. The similarity between edges e ik and e jk , analogous to Eq. (S5), is now: S(e ik , e jk ) = a i · a j |a i | 2 + |a j | 2 − a i · a j (S8)

S3.2 Multi-partite networks
A multi-partite network is a network in which the nodes can be divided into K disjoint sets and all links must terminate in two distinct sets. This creates additional constraints on the existence of certain edges which must be accounted for in both the link similarity and the partition density. Link similarity: The similarity measures, Eqs. (S5) and (S8), depend only upon connectivity, and therefore automatically account for multi-partite structure. The one change necessary is incorporating the forbidden connections between the same kind of nodes, which can be achieved by using the set of neighbors instead of the inclusive neighbor set when calculating the similarity.
Partition density: We must modify the definition of the partition density since a fully connected K-partite clique is much sparser


Using NLP Methods for the Analysis of Rituals

This paper gives an overview of an interdisciplinary research project that is concerned with the application of computational linguistics methods to the analysis of the structure and variance of rituals, as investigated in ritual science. We present motivation and prospects of a computational approach to ritual research, and explain the choice of specific analysis techniques. We discuss design decisions for data collection and processing and present the general NLP architecture. For the analysis of ritual descriptions, we apply the frame semantics paradigm with newly invented frames where appropriate. Using scientific ritual research literature, we experimented with several techniques of automatic extraction of domain terms for the domain of rituals. As ritual research is a highly interdisciplinary endeavour, a vocabulary common to all sub-areas of ritual research can is hard to specify and highly controversial. The domain terms extracted from ritual research literature are used as a basis for a common vocabulary and thus help the creation of ritual specific frames. We applied the tf*idf, 2 and PageRank algorithm to our ritual research literature corpus and two non-domain corpora: The British National Corpus and the British Academic Written English corpus. All corpora have been part of speech tagged and lemmatized. The domain terms have been evaluated by two ritual experts independently. Interestingly, the results of the algorithms were different for different parts of speech. This finding is in line with the fact that the inter-annotator agreement also differs between parts of speech.

Introduction
The structure and dynamics of rituals within and across different cultures and eras is the focus of a large interdisciplinary collaborative research center including 21 scientific fields ranging from Indology to Musicology. 1 The project presented in this paper complements traditional research methods prevalent in the humanities with computational linguistics analysis methods. In particular, we aim at employing data-driven approaches to detect regularities and variations of rituals, based on semi-automatic semantic annotation of ritual descriptions. Section 2 will present motivations for a corpus-based computational linguistics approach to ritual structure research and the project research plan. Section 3 illustrates our approach for semantic annotation and structural analysis of ritual descriptions. In Section 4 we report on first attempts to automatically acquire ritual-specific terminology. Section 5 concludes.

Computational Linguistics for Ritual Structure Research
Led by the observation of similarities and variances in rituals across times and cultures, ritual scientists are discussing the existence of a "ritual grammar", meaning an abstract underlying -and possibly universal -structure of rituals. It is highly controversial whether such structures exist, and if so, whether they are culture-independent or not. Our interdisciplinary project addresses this issue in a novel empirical fashion. Using computational linguistics methods, we aim at obtaining quantitative analyses of similarities and variances in ritual descriptions, thereby offering ritual scientists new views on their data. Ritual researchers analyze descriptions of complex event sequences, involving designated participants, objects, 1 "Ritual Dynamics": http://www.ritualdynamik.de places and times, usually encoded in natural language descriptions. However, the knowledge of patterns in ritual event sequences is often highly private among researchers devoted to particular cultures or scientific fields. Our project attempts to make these patterns overt, through computational linguistic analysis of the textual ritual descriptions. Computational Linguistics has developed semantic lexica and processing tools for the formal analysis of events and their predicate-argument structure, in terms of semantic roles. Based on such structured and normalized semantic representations of event sequences, we can identify recurrent patterns and variations across rituals by quantitative analysis. Frame Semantics (Fillmore et al., 2003), with its concept of scenario frames connected by frame relations and role inheritance, offers a powerful framework for the analysis of complex event sequences in ritual descriptions. Through annotation of word senses we can observe and analyze variations in the selectional characteristics of specific events and their roles across rituals. Finally, the creation of structured and normalized semantic representations for ritual descriptions will allow us to offer querying functionalities for ritual researchers, so that they can test and validate their hypotheses against a corpus of structurally analyzed ritual descriptions. For Computational Linguistics research, the project allows for the detailed investigations of techniques to compute event chains as representations of complex action sequences. Ritual descriptions typically consist of complex and often recurrent event sequences and use a restricted domain vocabulary and a closely circumscribed inventory of events and participants. This somewhat controlled domain gives us the opportunity for a detailed study of several phenomena at the interface between syntax and semantics (e.g. the computation of selectional preferences, the annotation of ritual-specific frames, and the modeling of event sequences in ontologies).

Project research plan
The project is divided into two consecutive stages of research, which concentrate on corpus creation and annotation and on the analysis and exploitation of the data, respectively.

Corpus creation and annotation
In the first stage, a comprehensive corpus of linguistically and semantically annotated rituals from different cultures is being created from natural language descriptions of rituals that are procured by experts. The semantic annotation follows the frame semantics paradigm (Fillmore et al., 2003) and comprises both general linguistic and ritual-specific annotation levels.
As we aim at an empirical basis for the conceptualization of the domain, we automatically identify relevant domain terms on the basis of scientific publications on ritual research which in turn can serve to establish a base vocabulary for the annotation with ritual-specific concepts.

Analyzing the structure of rituals
Based on the semantic annotation of ritual descriptions, logical and statistical methods will be deployed to detect recurring structures in ritual descriptions, as well as systematic variances. In close cooperation with the ritual experts, we will provide tools and explore methods for empirical, quantitative analysis of rituals, based on abstract semantic representations of rituals.

Related Work 2.2.1. Event Chains
Central to the structure of rituals are sequences of events and participants involved in these events. Thus, an important research topic is the detection and analysis of event chains in texts. The use of frame semantics as a useful abstraction layer for analyzing event chains has been investigated in Burchardt et al. (2006). A case study demonstrated how relations between instances of frames and roles can be inferred in context, using frame relations as well as contextual information, such as co-reference or syntactic association. Recently, a statistical approach has been proposed by Chambers and Jurafsky (2009) for unsupervised detection of event chains, using co-occurrence of a single discourse entity as argument of different verbs as well as co-reference information as criteria for extracting event chains. A related shared task on "linking roles in discourse" (Ruppenhofer et al., 2009) is being organized as part of SemEval 2010.

Term Extraction
Term extraction for specific domains has been a field of study for quite some time. Usually, two or more corpora are compared: Terms that appear significantly more often in a domain corpus compared to a domain "neutral" corpus are considered as domain terms. Frank et al. (1999) and Buitelaar and Sacaleanu (2001) use tf * idf to measure term relevance; Agirre et al. (2001) propose the use of the χ 2test. Reiter and Buitelaar (2008) successfully used χ 2 to detect medical domain terms.
An approach on domain term extraction that does not rely on contrasting corpora has been proposed by Yang et al. (2009). They transform the corpus into a graph containing nodes for candidate terms and edges between terms that appear in the same sentence. The PageRank algorithm is then used to weight the candidates, increasing the weight of term candidates co-occurring with term candidates that have a high weight in the same sentence.

Building an Annotated Corpus of Ritual Descriptions
As a basis for analysis, we use textual descriptions of rituals, which are supposed to include all relevant aspects of rituals.

Collection
We collect ritual descriptions from different sources. While some of them are found in lore (prescriptive sources), others were recorded in ethnological field studies (descriptive sources). This collection process has been started with rituals from Hinduism and Islam but we plan to adapt it for rituals from Ancient Egypt and the Middle Ages in central Europe.

Translations and Encodings
Ritual descriptions often contain specific lexemes that do not have a direct translation in English (or other languages): (1) He sweeps the place for the sacrificial fire with kuśa Kuśa is a Sanskrit term for a kind of grass that is very important in Vedic rituals. For this ritual, it is important to sweep with kuśa and not any other grass. As there is no English translation (the term "grass" refers to a more general concept), the translation is annotated with the original term. As the original name often contains non-Latin characters, the ritual descriptions are encoded in Unicode. For automatic processing, the original terms are eliminated, and later (re-)inserted in the semantic representation.

Fixed expressions
Most rituals contain fixed expressions. These may be prescribed pieces of text which have to be spoken or chanted while a ritual is performed (e.g., Our father in Christian church service).
There is no common way to refer to these fixed expressions. Sometimes, prayers or chants have a title or name; sometimes, first words or the refrain are given and the practitioner (or expert) can infer what is meant.
As most fixed expressions cannot be directly translated, we adopt them as unanalyzed expressions in a foreign language. We ask the ritual experts to mark them as such, so that for processing we can replace them with indexed place holders and re-insert them into the semantic representation. (NP (NN grass))))))) (. .)) Figure 2: Parse tree for (1): "with grass" is attached to the NP "the sacrificial fire". This analysis clearly does not conform with the interpretation of the sentence.

Meta data
Various types of meta data need to be collected for different cultures. For instance, it is important to distinguish descriptive and prescriptive ritual sources. We store this information in a growing set of meta data with each ritual description, using standardized sets of meta data tags if applicable.

Linguistic Preprocessing
The ritual descriptions are preprocessed with standard NLP tools. We use UIMA 2 as a pipeline framework which currently consists of the Stanford POS-tagger (Toutanova et al., 2003), Named Entity Recognizer (Finkel et al., 2005) and Parser . The fact that none of the above tools are trained on ritual descriptions or comparable texts causes processing problems. At the time of writing, we cannot yet provide a detailed quantitative analysis of how these tools perform. However, we can identify PP-attachment as a major recurrent problem:

PP-Attachment
PPs are quite common in the data, as becomes apparent in Example (1). The Stanford parser shows a tendency to attach PPs to closer phrases rather than building large structures (see Figure 2). 2 http://incubator.apache.org/uima/ In light of the frequent parse errors produced by the Stanford Parser, we currently experiment with using chunks produced by the OpenNLP Chunker as basis for the annotation.

Annotation
The annotation will be performed manually on syntactically parsed structures using the SALTO tool 3 . We will annotate two layers of semantic information.

General frame annotation
This annotation models the literal actions occurring while a ritual is performed. Ritual descriptions will be annotated with FrameNet frames, describing prototypical events together with their participants (denoted as frame elements). For most of the basic actions in rituals, an appropriate frame is already defined in FrameNet (80.8% of the verbs in the ritual descriptions collected so far [14,081 tokens] are known lexical units). For actions that are not represented in FrameNet, we will carefully add new frames and integrate them into the FrameNet hierarchy (e.g., frame relations, semantic types).

Ritual specific annotation
In addition to the literal actions they denote, most events have a ritual-specific meaning or intention (e.g., sweeping a place in order to purify it). We will add a second layer with ritual-specific frames from a newly created frame inventory. The ritual-specific frames will be linked to the general frames via the annotated lexical units and related to each other by frame relations where appropriate. This network of ritual frames will form the basis of a ritual ontology. A framework for the integration of an annotated corpus with an ontology has been presented by Burchardt et al. (2008).

Detecting Ritual Structure
As proof of concept for the types of analyses we can offer to ritual scientists, we constructed representations for a number of close variations of rituals. Figure 1 shows a partial semantic representation of two such rituals. We extracted the event sequences, one starting with PLACING, one with CHANGE POSTURE. The sequences share the frames TAK-ING and STATEMENT. The co-reference chains are denoted by curved lines. This is one way in which we plan to extract and visualize common subsequences in rituals.

Domain Term Extraction
As the ritual descriptions we collect come from different cultures, epochs and regions, the providing researchers come from various disciplines and speak different "scholarly languages". To support normalization of the used vocabulary, we collected a corpus of scientific literature from the various disciplines. From this we extract relevant terms for rituals in general, using three different approaches.

Corpora
Some of our approaches employ contrasting, non-domain corpora in order to identify domain terms. We use two different non-domain corpora, one general corpus (BNC) and one for scientific language with mixed subjects (BAWE).

BNC
The British National Corpus (BNC, 2007) consists of 100 million tokens from various domains and sources. We use both the written and spoken part of the BNC.

BAWE
The British Academic Written English corpus 4 contains 2761 documents written by students from various disciplines and levels of study (starting with undergraduate students) that were somewhat cleaned. In total, the corpus contains 6.3 million tokens. The corpus is already sentence split, but we applied automatic (heuristic) tokenizing, part-of-speech-tagging 5 and lemmatization (Toutanova et al., 2003).

Approaches
In the following, a term always includes its part of speech. Thus, the noun "worship" is a different term (and term candidate) than the verb "worship". As candidates, we used all nouns, verbs and adjectives occurring in the ritual literature corpus.

TF*IDF
The TF * IDF measure for termhood has been studied extensively in information retrieval. Let freq t,d be the frequency of term t in document d, df t be the number of documents in which term t appears, and D the number of documents. The TF*IDF score of a term t in a document d is then calculated as shown in (3) and (4). As we are not aiming at identifying the most relevant document for a given term (as is the standard use case for TF*IDF), we need to slightly change the view on documents. Each corpus is combined in one document, so that we have three documents. Document frequency (df t ) is the number of corpora in which the term t appears.

Chi 2
For the χ 2 measure, the domain corpus was set in contrast to the BNC and BAWE corpora. We calculated χ 2 as described in Manning and Schütze (1999), but based on lemma-and POS-information and the summed frequencies over both non-domain corpora. The raw χ 2 values are logarithmized for normalization and scaled to the interval [0, 1].

PageRank
The third approach on domain term extraction follows Yang et al. (2009). For each candidate term, a node in a graph is created. If two (candidate) terms co-occur in the same sentence, an edge between the corresponding nodes is added to the graph. The relevance of individual term nodes is then calculated using the PageRank (Brin and Page, 1998) algorithm. The PageRank algorithm gives higher weights to nodes that are connected to other nodes with a high weight -The relevance score of a term increases if it co-occurs with a term that has a high relevance score.

Evaluation
As there is no gold standard for the domain of ritual science, we asked two ritual experts to annotate the terms extracted by our approaches. From each approach, we selected the 10 best ranked noun, verb and adjective terms, so that in total 90 terms have been annotated. The terms have been classified into three classes (yes, maybe, no) by two ritual experts independently. The overall kappa for this annotation is κ = 0.35, with differences between part-of-speech categories. The highest agreement between the annotators was achieved on adjectives (κ = 0.49). Interestingly, 36% of the agreed adjective terms are rejections. With a kappa value of 0.35, the agreement on verbs seems to be somewhat fair. The agreement was very low on nouns, with κ = 0.22. Because of this low agreement, we will also look at the data produced by the individual annotators A1 and A2 in the following discussion. In general, A1 seems to be much more liberal, annotating "maybe" in 58% of all cases (A2: 19%). The majority class for A2 is "no" (51%, A1: 14.4%). We also found inconsistencies within the data annotated by A1 (granth 6 is annotated as "maybe" in one approach and "no" in another). Table 1 shows the results for the different term lists. Partial agreement is achieved when one annotator annotated yes (or no) and the other one maybe. In full agreement, both annotators annotated yes (or no). From the terms extracted with the TF*IDF approach, 13.3% are considered a domain term by both annotators. As mentioned above, the annotator's judgement differs with respect to part of speech of the term. Among the nouns, only 10% of the terms are judged as domain terms by both annotators (verbs: 20%, adjectives 10%). If one annotator is allowed to be unsure, i.e., annotating the term as "maybe" (partial agreement), the number of terms increases to 23.3% (with similar increases for each part of speech). For wrongly extracted terms, the agreement between the annotators is much smaller. Among the adjectives, the annotators agreed that 50% of the terms are false positives, while there was no extracted noun or verb that was rejected by both annotators. According to annotator A1, all the nouns and verbs extracted by the TF*IDF approach are certainly or maybe domain terms. Several very generic adjectives (earlier, . . . ) are annotated as non-domain in agreement with A2. A2 rejected most of the nouns, verbs and adjectives. Only 10% of the nouns, 20% of the verbs and 30% of the adjectives are annotated positively. The overall numbers are better for the Chi 2 approach. For 40% of the terms, both annotators fully agree that it is a domain term. 56.6% of the extracted terms are judged as domain relevant by at least one annotator (while the other specified "maybe"). Again, for different parts of speech, we get different results. While the results of the TF*IDF approach do not show a clear tendency, the χ 2 approach performs clearly better for adjectives than for verbs and nouns. If partial agreement is allowed, 80% of the adjectives are considered a domain term, while only 30% of the nouns and 60% of the verbs are judged as domain terms. Looking at the data, we find that the 20% of the nouns that are rejected by both annotators can both be traced to errors from the part of speech tagger: Both www and varanasi 7 are not verbs. None of the annotators rejected any one of the adjectives. A1 annotated 60% of them as domain-term, A2 80%. Again, nouns seem to be much more problematic. Both rejected most of the nouns (A1: 30% yes; A2: 20% yes). For verbs, about half of the terms are accepted (A1: 40%; A2: 60%).
6 Adi Granth is the holy scripture of the Sikhs. 7 Varanasi is a city in Northern India and thus a proper name.
The PageRank approach scores much lower than the others for all three parts of speech. In fact, not a single verb extracted with this algorithm was judged as a domain term, even if partial agreement is allowed. Looking at the list of verbs, this is not surprising as most of them are very general (to do, to be, to have, . . . ). The same observation can be made for the other parts of speech. The extracted terms are clearly often used (and useful) in the domain, but do not separate the ritual research domain from others. The annotations for the terms extracted using PageRank support what we mentioned above: Annotator A2 is much more strict. While A1 rejects only 13% of the terms, A2 rejects 60% across all word classes.

Conclusions
We presented motivations and the research plan of an interdisciplinary project that can offer insights for ritual science, but also for CL. We discussed problems we face when dealing with data from humanities, especially in the domain of rituals. We presented the work chain for corpus creation, annotation and exploitation for the structural analysis of rituals. We reported on preliminary results for the extraction domain terminology, which will provide a base vocabulary for ritual-specific semantic annotation. The next steps will be the semantic annotation of ritual descriptions on a larger scale and the deployment of analysis techniques to identify structural elements and variability in rituals.