Limits of Chow groups, and a new construction of Chern-Schwartz-MacPherson classes

格式：pdf
大小：315.92 KB
文档页数：23

下载文档原格式

Robust membership management for ad-hoc groups

Robust Membership Managementfor Ad-hoc GroupsSilja Mäki,Tuomas Aura,Maarit HietalahtiHelsinki University of TechnologyLaboratory for Theoretical Computer ScienceFIN-02015HUT,Finland{Silja.Maki,Tuomas.Aura,Maarit.Hietalahti}@hut.ﬁAbstractIn ad-hoc networks,the network nodes or users often form peer groups.The members of a group may share an application,a physical location,or ad-ministrative tasks.Deﬁning who is a member of the group is also theﬁrst steptowards establishing a shared secret key for secure communications.Groupmembership management involves adding and removing nodes in the group,as well as a method for authenticating the group members.In this paper,wepresent a fully distributed,certiﬁcate-based system for group membershipmanagement.It is designed to suit highly dynamic ad-hoc networks wherecommunications is sporadic and nodes often fail unexpectedly.1IntroductionAd-hoc networks are constructed and maintained without the help of permanent administration and preexisting infrastructure.They are often wireless and mobile. The size of ad-hoc networks may vary from a few connected nodes to hundreds or thousands of nodes.Some examples of ad-hoc networks are networks of per-sonal,household and ofﬁce appliances,and mobile radio networks for rescue,law-enforcement and military operations.The security of most traditional networks relies on the existence of a permanent, specialized network administration that deﬁnes the security policy and provides the infrastructure for implementing it.In ad-hoc networks,all the services,including a security infrastructure,must be created from scratch and administered by the nodes that decide to form the network.A basic concept in many ad-hoc networks is a group of users or network nodes.A group is a set of entities that want to communicate with each other and to co-operatefor some purpose.The need for forming a group could be a shared application, physical location,or administrative tasks that associate some nodes with each other. Forming a group may also be theﬁrst step towards creating a shared secret,which will be used to separate the insiders from the outsiders.Membership management of groups involves adding and removing nodes in the group,as well as providing a method to authenticate the group members.A node may prove its membership in a group also to nodes that are not members of the group.The most important security functions for a group are the following: mutual authentication of group membersauthentication of group members to outsidersauthentication of members with special roles in the membership manage-mentmutual authentication for group key-exchange.Ad-hoc groups need cope with with the special characteristics of ad-hoc networks. The connections are unstable,and energy resources of the nodes are scarce.Ad-hoc networks generally lack infrastructure and are vulnerable to security threats.As a consequence,the groups should be managed as lightly as possible,and indepen-dently fromﬁxed network services and from each other.The management should be distributed and tolerant to failures of physical security.The groups should be easy to construct and modify,in a true ad-hoc manner.We have made the following choices in designing our protocols:The membership is dynamic.New members are admitted and old ones leave the network.The membership of known physically compromised nodes,or ones whose integrity is suspected,can be revoked.However,we trust most nodes to leave voluntarily and,due to the sporadic communications and un-regulated relations in ad-hoc networks,provide only best-effort revocation.The membership protocol must be resistant to communications failures.The connections in wireless networks may fail temporarily and the network may be partitioned at times.The membership protocols must be resistant to the unexpected and perma-nent removal of nodes.Connections in an ad-hoc network may fail per-manently,e.g.when a node leaves the operating area,its battery becomes exhausted or,in military applications,it is destroyed.Due to the frequent communication and power failures and poor physical se-curity,all functionality is distributed to avoid single points of failure.There-fore,the authority to admit new members and to revoke old ones is dis-tributed to several nodes.However,we allow each authorized node to make decisions alone and do not resort to threshold schemes or other separation of powers.This is because the ad-hoc networks are often deployed in circum-stances where fast decision making is more desirable than absolute security. Our scheme for group membership management is based on public key cryptog-raphy and on the use of signed certiﬁcates.The members are represented by their public signature keys,and each group has a public signature key to represent the group as a whole.Certiﬁcates signed by the group key are used to indicate the membership of the nodes.1.1CertiﬁcatesCertiﬁcates are an application of public key cryptography.A certiﬁcate is a mes-sage signed with the private key of a certiﬁer.In traditional networks,certiﬁcates signed by a trusted certiﬁcation authority(CA)typically bind the identity of the key owner to the public key(identity certiﬁcates),or they bind some access rights to the name or to the public key of an entity.In our group management scheme,cer-tiﬁcates signed by the group key are used to bind the status of a group member or leader to the member’s public key.We assume that the public keys are distributed through secure channels such as personal contact.We make no use of identity certiﬁcates or CAs.This kind of architecture is called key oriented.The authority of a certiﬁcate depends on whether the issuer is trusted or not.Cer-tiﬁcates delegate trust:if one trusts the issuer,then one is assumed to trust the receiver of the certiﬁcate on what the certiﬁcate states.Certiﬁcation chains involve several subsequent certiﬁcates delegating some authority from a party to another. Trust is either considered transitive,so that if theﬁrst issuer in the chain is trusted then also the last certiﬁcate in the chain is trusted,or the re-delegation of the rights may be forbidden.A certiﬁcate may have an expiration date.After the validity period is over,the certiﬁcate loses its effect.A chain of certiﬁcates is valid only if all the certiﬁcates in the chain are valid.The length of the validity period is a trade-off between the security improvement allowed by a periodic review of the delegation and the cost of renewing the certiﬁ-cates.If the private key of the receiver of the certiﬁcate is compromised,frequent refreshing prohibits long-term misuse of a certiﬁcate.On the other hand,the more often the certiﬁcates have to be re-issued,the more expensive the system is to maintain,and the more likely it is that secure communication is unavailable.In particular,the expiration of a certiﬁcate in a chain affects also the rights of all the following entities in the chain.Thus,frequent expiration may cause the systemwith long certiﬁcate chains to become unreliable.In most systems,certiﬁcates may be revoked by the issuer of the certiﬁcate,and sometimes by other authorities.Lists of the revoked certiﬁcates have to be dis-tributed throughout the network.In a small network this may be an effective and rapid way to react against possible security failures.In a large distributed system, the time margin between the revocation and the time the information reaches a user may be so long that attacks using revoked certiﬁcates cannot be fully prevented. Revocation is usually combined with limited validity periods for certiﬁcates so that the revocation lists or servers need only to remember those revoked certiﬁcates that have not yet been expired.Again,there is a trade-off between the size of revocation lists and how often the certiﬁcates need refreshing.2Related workThe nodes of an ad-hoc network are often more equal than those in a traditional communications system.This is due to the lack of permanent authorities.Conse-quently,security mechanisms for ad-hoc networks also treat the nodes with relative equality.While communications security has traditionally been based on point-to-point communication with trusted servers,the basis for the security of an ad-hoc system is,in many of the proposed architectures,multicast inside a group.For example,the ad-hoc network management protocol by Chen et al.[6]is based on secure multicast that should be received only by a given group of nodes.Un-fortunately,the security features of the protocol are less mature than the network management part.The most common security function for an ad-hoc group is to establish a secure communications channel between the members.In practice,this means creating a shared session key for the encryption and authentication of data that will be sent between the members.Efﬁcient protocols for a group key exchange have been pre-sented,for example,by Burmester and Desmedt[4],and by Ateniese et al.[2]. Asokan and Ginzboorg[1]discuss key exchange in ad-hoc networks with empha-sis on the robustness of the protocol against the failure of some nodes.It should be noted that a shared secret key does not protect the group members from eavesdrop-ping and impersonation by each other.The idea is that the group members trust each other with respect to the purpose of the group.End-to-end security must be used or a new group must be be established when any group member is not trusted to access some data.Multicast is the preferred way of communicating in a radio network because it saves the bandwidth in comparison to sending separate copies of a message to in-dividual receivers.A good overview of multicast security by Gong and Shacham[11]also discusses the extension of Internet multicast protocols to mobile net-works.However,their emphasis is on traditional mobile networks with aﬁxed support architecture.Secure group communication for mobile stations has been implemented in the TETRA mobile network for public safety applications[15].It relies on manual distribution of the group key either on smartcards or over the air. The IP[12]multicast is used mostly for the distribution of public data streams on the Internet.The number of receivers for these streams can be extremely large. Hence,the protocols are designed to minimize the load on the server.They allow anyone to subscribe to a stream,i.e.,to join the multicast group,without any per-mission from the sender.Receivers can be selected securely by encrypting the data stream and by distributing the session key only to the authorized receivers.This lesson can be extended to all group communication:allow anyone to route and to receive the encrypted data and distribute the decryption key only to the group members.Another context where secure group multicast has been used is in the synchro-nization of process groups in distributed computer systems.For example,the Isis distributed programming toolkit[13]maintains synchrony between process groups distributed to several sites and provides some protection against corrupted sites. The Isis protocol has the interesting detail that the public key of the group is a part of the group address.Isis requires reliable communication channels and a trusted central authentication service.To our knowledge,no completely decentralized systems for group membership management have been presented in the literature.There is usually a group leader or other trusted entity that manages the group.If this central entity fails,the group will cease to exist.The reason for the centralized solutions is probably the need to keep track of the group membership or to make decisions about it in one place. Nevertheless,we believe that a more distributed protocol for group membership management matches better the reality of ad-hoc networks.When communication between network elements is sporadic and nodes are likely to be removed unex-pectedly,all group management functions must be distributed to several leaders who may act independently.Our protocols is based on public-key certiﬁcates.Implementations could use stan-dard a key-oriented certiﬁcate format such as the SPKI authorization certiﬁcate [10,9]or the one speciﬁed by the KeyNote trust-management system[3].SDSI [14]names can also be used to implement groups.The downside of the increased distribution is that it becomes difﬁcult to obtain a snapshot of the membership and revocation of member rights cannot be done as reliably as in centrally controlled groups.In our system,membership may be revoked by group leaders but there is no guarantee of the revocation information reaching all the entities outside the group in anyﬁxed time.Naturally,applicationsmay provide more reliable propagation of the revocation lists.In comparison to other systems based on certiﬁcates,we have chosen to revoke membership in a group and not the signature keys,as in most systems based on the X.509certiﬁcate standard[5],or the individual certiﬁcates,as in SPKI.Threshold schemes have been frequently suggested for improving the security of mobile networks where the nodes are in physical danger.Zhou and Haas[16], for instance,propose the use of threshold schemes and signatures[8]in order to prevent one or a few compromised nodes from signing messages for the group.A threshold signature must be signed by several members of the group before it becomes valid.We found that although threshold schemes clearly improve the security of the system,they can easily lead to the denial of service.In practical applications,protection against compromised nodes is often less important than that decisions are made fast and actions taken immediately.This is true even in law enforcement and military applications where the network nodes are frequently exposed to a real physical threat.3Managing group membership with certiﬁcatesOur system for group membership management is based on public-key signatures and on the use of public-key certiﬁcates.A group consists of members,which are identiﬁed by their public keys.There is also a public key representing the group as a whole.Some members of the group are leaders,which have the right to admit new members to the group.Each member of the group possesses a membership certiﬁcate,which states that the entity is indeed a member of the group.The certiﬁcate is signed by a leader of the group.3.1The basic group structureTo create a new group,one generates a new signature key()for the group, the group key.This group key will be used as the identiﬁer of the group and to certify the members.The public keys of the members are called the member keys. Originally,when a new group is created,the group key is the only member key of the group.To become a member of a group,an entity with a public key needs a member-ship certiﬁcate signed by the group key.Basically,a certiﬁcate is issued to the public key of the member and it states that the key is a member of the group .The membership certiﬁcates can be veriﬁed with the public group key.Since the group key is the group identiﬁer,everyone doing business with the group willMember4owns K4Leader1generates new key KGMember3owns K3Member2owns K2Figure 1:A simple group with 4membersautomatically know it.A membership certiﬁcate contains the following information:the group identiﬁer (i.e.the public group key)the public member keya validity perioda signature signed with the group keyThe group key is called a leader key ,since it can be used to add new members to the group.Accordingly,the owner of the group key is the leader of the group.Note that anyone capable of generating a fresh public key pair may start a new group and act as the leader of the group.A group with four member keys (including the group key)is illustrated in Fig.1.(For simplicity,the validity periods of the certiﬁcates are not shown in the ﬁgure.)To verify that Member 2is a member of the group ,one has to obtain its membership certiﬁcate,to verify that the signature on the certiﬁcate is properly signed by ,and to verify that Member 2possesses the member key ,which is stated on the certiﬁcate.3.2Increased robustness with multiple leadersIn groups of the the previous section,the owner of the group key is the only member who could let new members join the group.In an ad-hoc network,a node may be out of reach at a moment,e.g.,due to a routing problem or to a technical failure of the node.If the leader cannot temporarily be reached,all decisions related toLeader1Member4owns K4owns K3Leader3Member5owns K5Figure2:A group with multiple leadersthe membership must wait until a connection is established again.If the leader is permanently removed from the system,the only way to make any changes to the membership is to establish a new group with a new leader.In order to increase the robustness of the membership management,the authority of the leader must be distributed to several members.We do this by letting the original leader(i.e.the group-key owner)delegate the leadership to other members.It can authorize other keys to act as equivalent leaders by issuing leader certiﬁcates.All leaders of a group are also its members.Hence,a leader certiﬁcate is a form of member certiﬁcate,and the certiﬁcates have the following additionalﬁeld: member or leaderSince the new leaders have an equivalent authority with the original leader,they all may admit new members and new leaders to the group by signing certiﬁcates with their own keys.Figure2shows an example of a group with multiple leaders.In order to prove membership in the group,a member that has been certiﬁed di-rectly by the group key needs its own private key and the membership certiﬁcate.A member that has been certiﬁed by another leader needs all the certiﬁcates in the path from the group key to its member key.Hence,when a leader certiﬁes other leaders or members,it must pass along all the certiﬁcates that prove its own status as a leader in the group.This way,a chain of certiﬁcates is formed from the group key to each member key.Fig.2illustrates the multiple leaders.For example,when Member5of Fig.2 joins the group,he gets the membership certiﬁcate signed by Leader2and the leader certiﬁcate issued to Leader2signed by.The latter certiﬁcate proves the authority of Leader2.When Member5wants to prove its membership,it presents both certiﬁcates and proves its possession of the key.The manner in which the leaders and members are added to the group creates a treestructure.The group key is at the root of the tree and the members without leader status are at the leaves.If any one of the leaders is removed from the system either temporarily or perma-nently,the other leaders may still continue their operation.Thus,the distribution of authority increases the robustness of the network against the loss of nodes or connections.A disadvantage of having multiple leaders acting independently may be that there is no single entity aware of all the members of the group.3.3Protection against the compromise of keysWe wish to protect the group membership protocol against the compromise of keys. The nodes of an ad-hoc network are often exposed to physical danger and,regard-less of any safeguards,it is likely that some private keys or equipment containing them will sometimes fall into the hands of the adversary.Reconstitution of the group is a secure and often recommendable way to continue with the trusted members only.However,full reconstitution may acquire time as some of the trusted nodes might occasionally be out of reach.The members of a group also need some instant mechanisms for canceling the membership of a single key without sacriﬁcing membership of the other,still trusted members. Unfortunately,canceling a membership that has already been granted is not easy. The membership certiﬁcates may be created,stored and veriﬁed concurrently at different parts of the system.There are basically two ways of getting rid of un-trusted members:membership expiration and membership revocation.Group reconstitution To replace a group with a new one,a new group key is generated and new membership and leadership certiﬁcates are issued to the old members.Group reconstitution may be done periodically or when there has been enough changes in the group membership.Because of its conceptual simplicity, group reconstitution should be used as the primary protection against compromised members.It is possible to to create the new group while the old one is still func-tional and gradually shift from using the old one to the new one.That way,the new group key and the new certiﬁcates can be propagated to all necessary nodes before the old group key is abandoned.(The subgroup certiﬁcates presented in Sec.4.1 can be used to attach the old group temporarily as a subgroup of the new one.) Membership expiration The membership certiﬁcates may have a validity period that is decided by the issuer.By choosing short validity periods and by refresh-ing the certiﬁcates frequently,the leaders of the group can periodically review the members’status.The expiration mechanism has the major advantage that,once amembership certiﬁcate has expired,it can be simply forgotten.No communication or storing of the expired certiﬁcates is needed.On the other hand,the members that want to retain their membership have to periodically obtain new certiﬁcates. The expiration also relies on loosely synchronized clocks at every network node.Importantly,the issuer of short-lived certiﬁcates has to periodically consider the reliability of the member.Thus,the limited lifetime keeps up awareness of the security risks and protects against long-term accumulation of compromised mem-bers.The issuers may adjust the certiﬁcate lifetime for each member depending on the cost of distributing the refreshed certiﬁcates and the likelihood of a compro-mise.For example,the cost of distribution is higher for a leader certiﬁcate as the refreshed certiﬁcate must be passed down to every member admitted by that leader earlier.Therefore,the leader certiﬁcates are likely to have fairly long lifetimes. Membership revocation Revocation enables the network to react immediately against the possibility of a security failure.However,when a decision is made to revoke a membership,the information about the revocation must be propagated to all the parts of the system where relevant certiﬁcates may be used.Distribution over unreliable connections may cause that the information about a revoked mem-bership may not reach all the entities that need it.Delays in the propagation of the revocation data may also be considerable.Hence,there will always be a margin of error where a revoked member might be accepted as a valid one.We have chosen to give all the leaders of a group the right to revoke themselves and any other leaders and members of the same group.They do this by signing revocation lists of group-key pairs.The lists and additions to them are propagated in a best-effort manner to all the members of the group and to other parties that may verify the group membership.The exact method of distributing the information depends on the application and on the network management and routing protocols. Members should be revoked only when there is a reason to suspect that the private key has been fallen into the hands of an adversary.The cost of distributing the revocation lists is too high for anything but emergency situations.For example,if the private key has only been lost,revocation is not needed.Leaders may be re-voked just like ordinary members but the operation will also affect all the members certiﬁed by the revoked key.If a private leader key has been compromised,the adversary in the possession of the key may revoke other members and leaders.Revocation lists signed by already revoked leader keys must nevertheless be accepted.The reason is that if the com-promise is noticed and the leader key revoked,the adversary could timestamp its revocation lists with a date prior to its own revocation.So,in a case where two leaders revoke each other,it is impossible to know which one of the leaders is really the compromised one.Therefore,both keys must be considered revoked.3.4Increased robustness with erased group keys and redundant cer-tiﬁcatesOne effect of the expiration or revocation of a leader key is that it causes not only the removal of that leader but also affects every member below the removed leader in the tree structure formed by the certiﬁcates.The result is particularly dramatic if the membership of the group key itself is revoked.For if the group key becomes under suspicion and needs to be revoked,the whole group perishes. Revocation of the group key may be desired when one wants to replace the group key with a new one and reconstitute the entire group.However,unexpected revo-cation of the group key may also cause confusion.In this section,we discuss some techniques to counter the effects of removing possibly corrupted leaders from the group.Erasing the group key A perfect way of protecting the private key against a compromise is to erase it.An erased key cannot be recovered or misused in any way.The certiﬁcates signed with the erased key continue to be valid and they can still be veriﬁed with the public key.Of course,the erased key cannot issue any new certiﬁcates.A private key is at most a few kilobits long and therefore relatively easy to purge from the memory.If one regularly maintains large sets of keys,the techniques of Crescenzo et al.[7]may be used to erase the keys reliably.In our group context,the newly generated private group key can be used to certify a few leaders and then erased.Several leaders should be certiﬁed with the group key so that if the membership of one of them must be revoked,the remaining leaders can still continue to administer the group.The group members should be informed that the group key is protected and cannot be compromised.This way,they know that the group key will never be revoked.For example,Leader1in Fig.3uses the group key to certify its own key and another key as leaders of the group.After signing the certiﬁcates,the group key is erased from Leader1’s memory.The leader certiﬁcates signed with the erased group key must have long enough lifetimes.The certiﬁcates signed by a key cannot be refreshed after erasure of the key,so when these leader certiﬁcates are about to expire,the group needs to be reconstituted.Issuing redundant certiﬁcates Erasing the private group key removes a single point of failure in the sense that there is no single key whose compromise would disable the entire group.However,large parts of the certiﬁcate tree can still be removed from the group by revoking one of the leaders certiﬁed by the group key.A member can alleviate this threat by obtaining multiple independent certiﬁcates. The leaders may also issue redundant certiﬁcates to each other.and erases KG signs certificates,owns K4Member3owns K3Figure 3:Erased group keyIn Fig.4,even if Leader 2loses its authority (its leader certiﬁcate expires or its membership is revoked),Member 4still remains a member in the group.Note that if the membership of either Member 3or Member 4should be revoked,redundant certiﬁcates do not prevent or complicate the revocation in any way.In fact,by revoking the whole membership of an untrusted member,the leader need not be aware of the certiﬁcates that have been issued to the compromised member.This is why we have chosen to revoke the memberships and not single membership certiﬁcates.In the tree structure formed by the certiﬁcates,the chains can become too long to be practical.The deeper the tree,the higher the cost of storage and veriﬁcation of the certiﬁcate chains.The lengths of the certiﬁcation chains also tend to increase when keys are erased.This can be countered by letting the members obtain redun-dant certiﬁcates directly from top-level leaders and use them instead of the original certiﬁcates given when the members ﬁrst joined the group.The redundant certiﬁcates confuse the tree structure of the group,and there will exist many certiﬁcation chains for one member instead of the one leading from the member to the root.A member should be aware of the different chains,so that when one chain is broken,he knows to use the others.4Relations between groupsThe groups as deﬁned so far are independent of each other.All member and leader certiﬁcates include the group identiﬁer and they have effect only on the member-ship of that group.The same is true for the entries of a membership revocation list.The only way the groups may interact is that a key may be a member in more than one group,or a physical entity may possess several keys that are members of different groups.Public-key certiﬁcates,however,are capable of expressing far。

Collaborative Governance in Theory and Practice

JPART18:543–571 Collaborative Governance in Theoryand PracticeChris AnsellAlison GashUniversity of California,BerkeleyABSTRACTOver the past few decades,a new form of governance has emerged to replace adversarial and managerial modes of policy making and implementation.Collaborative governance,as it has come to be known,brings public and private stakeholders together in collective forums with public agencies to engage in consensus-oriented decision making.In this article, we conduct a meta-analytical study of the existing literature on collaborative governance with the goal of elaborating a contingency model of collaborative governance.After review-ing137cases of collaborative governance across a range of policy sectors,we identify critical variables that will inﬂuence whether or not this mode of governance will produce successful collaboration.These variables include the prior history of conﬂict or cooperation, the incentives for stakeholders to participate,power and resources imbalances,leadership, and institutional design.We also identify a series of factors that are crucial within the collaborative process itself.These factors include face-to-face dialogue,trust building,and the development of commitment and shared understanding.We found that a virtuous cycle of collaboration tends to develop when collaborative forums focus on‘‘small wins’’that deepen trust,commitment,and shared understanding.The article concludes with a discus-sion of the implications of our contingency model for practitioners and for future research on collaborative governance.Over the last two decades,a new strategy of governing called‘‘collaborative governance’’has developed.This mode of governance brings multiple stakeholders together in common forums with public agencies to engage in consensus-oriented decision making.In this article,we conduct a meta-analytical study of the existing literature on collaborative governance with the goal of elaborating a general model of collaborative governance. The ultimate goal is to develop a contingency approach to collaboration that can highlight conditions under which collaborative governance will be more or less effective as an Early versions of this article were presented at the Conference on Democratic Network Governance,Copenhagen,the Interdisciplinary Committee on Organizations at the University of California,Irvine,and the Berkeley graduate seminar Perspectives on Governance.We thank the participants of these events for their useful suggestions and Martha Feldman,in particular,for her encouragement.We also thank two anonymous reviewers for their thoughtful and useful comments.Address correspondence to the author at cansell@ or aligash@.doi:10.1093/jopart/mum032Advance Access publication on November13,2007ªThe Author2007.Published by Oxford University Press on behalf of the Journal of Public Administration Researchand Theory,Inc.All rights reserved.For permissions,please e-mail:journals.permissions@approach to policy making and public management.1In conducting this meta-analytic study,we adopted a strategy we call ‘‘successive approximation’’:we used a sample of the literature to develop a common language for analyzing collaborative governance and then successively ‘‘tested’’this language against additional cases,reﬁning and elaborating our model of collaborative governance as we evaluated additional cases.Although collaborative governance may now have a fashionable management cache´,the untidy character of the literature on collaboration reﬂects the way it has bubbled up from many local experiments,often in reaction to previous governance failures.Collabo-rative governance has emerged as a response to the failures of downstream implementation and to the high cost and politicization of regulation.It has developed as an alternative to the adversarialism of interest group pluralism and to the accountability failures of manageri-alism (especially as the authority of experts is challenged).More positively,one might argue that trends toward collaboration also arise from the growth of knowledge and in-stitutional capacity.As knowledge becomes increasingly specialized and distributed and as institutional infrastructures become more complex and interdependent,the demand for collaboration increases.The common metric for all these factors may be,as Gray (1989)has pointed out,the increasing ‘‘turbulence’’faced by policy makers and managers.Although Susskind and Cruikshank (1987),Gray (1989),and Fung and Wright (2001,2003)have suggested more general theoretical accounts of collaborative governance,much of the literature is focused on the species rather than the genus .The bulk of the collaborative governance literature is composed of single-case case studies focused on sector-speciﬁc governance issues like site-based management of schools,community po-licing,watershed councils,regulatory negotiation,collaborative planning,community health partnerships,and natural resource comanagement (the species).2Moreover,a num-ber of the most inﬂuential theoretical accounts of this phenomenon are focused on speciﬁc types of collaborative governance.Healey (1996,2003)and Innes and Booher (1999a,1999b),for example,provide foundational accounts of collaborative planning,as Freeman (1997)does for regulation and administrative law and Wondolleck and Yaffee (2000)do for natural resources management.Our goal is to build on the ﬁndings of this rich literature,but also to derive theoretical and empirical claims about the genus of collaborative governance—about the common mode of governing.DEFINING COLLABORATIVE GOVERNANCEWe deﬁne collaborative governance as follows:A governing arrangement where one or more public agencies directly engage non-state stakeholders in a collective decision-making process that is formal,consensus-oriented,and deliberative and that aims to make or implement public policy or manage publicprograms or assets.This deﬁnition stresses six important criteria:(1)the forum is initiated by public agencies or institutions,(2)participants in the forum include nonstate actors,(3)participants engage directly in decision making and are not merely ‘‘consulted’’by public agencies,(4)the 1Thomas (1995)develops a contingency perspective on public participation,though it aims more broadly and is developed from the perspective of public managers.2A smaller group of studies evaluates speciﬁc types of collaborative governance at a more aggregated level (for example,see Beierle [2000],Langbein [2002],and Leach,Pelkey,and Sabatier [2002]).Journal of Public Administration Research and Theory544Ansell and Gash Collaborative Governance in Theory and Practice545 forum is formally organized and meets collectively,(5)the forum aims to make decisionsby consensus(even if consensus is not achieved in practice),and(6)the focus of collab-oration is on public policy or public management.This is a more restrictive deﬁnition thanis sometimes found in the literature.However,the wide-ranging use of the term has,as Imperial notes,been a barrier to theory building(Imperial2005,286).Since our goal is to compare apples with apples(to the extent possible),we have deﬁned the term restrictivelyso as to increase the comparability of our cases.One critical component of the term collaborative governance is‘‘governance.’’Much research has been devoted to establishing a workable deﬁnition of governance that is bounded and falsiﬁable,yet comprehensive.For instance,Lynn,Heinrich,and Hill (2001,7)construe governance broadly as‘‘regimes of laws,rules,judicial decisions,and administrative practices that constrain,prescribe,and enable the provision of publicly supported goods and services.’’This deﬁnition provides room for traditional governmental structures as well as emerging forms of public/private decision-making bodies.Stoker,onthe other hand,argues:As a baseline deﬁnition it can be taken that governance refers to the rules and forms that guidecollective decision-making.That the focus is on decision-making in the collective impliesthat governance is not about one individual making a decision but rather about groups ofindividuals or organisations or systems of organisations making decisions(2004,3).He also suggests that among the various interpretations of the term,there is‘‘baseline agreement that governance refers to the development of governing styles in which bound-aries between and within public and private sectors have become blurred’’(Stoker1998, 17).We opt for a combined approach to conceptualize governance.We agree with Lynn, Heinrich,and Hill that governance applies to laws and rules that pertain to the provision ofpublic goods.However,we adopt Stoker’s claim that governance is also about collective decision making—and speciﬁcally about collective decision making that includes bothpublic and private actors.Collaborative governance is therefore a type of governance inwhich public and private actors work collectively in distinctive ways,using particular processes,to establish laws and rules for the provision of public goods.Although there are many forms of collaboration involving strictly nonstate actors,ourdeﬁnition stipulates a speciﬁc role for public agencies.By using the term‘‘public agency,’’our intention is to include public institutions such as bureaucracies,courts,legislatures,andother governmental bodies at the local,state,or federal level.But the typical public in-stitution among our cases is,in fact,an executive branch agency,and therefore,the term‘‘public agency’’is apt.Such public agencies may initiate collaborative forums either tofulﬁll their own purposes or to comply with a mandate,including court orders,legislation,or rules governing the allocation of federal funds.For example,the Workforce InvestmentAct of1998stipulates that all states and localities receiving federal workforce develop-ment funds must convene a workforce investment board that comprised public and privateactors in order to develop and oversee policies at the state and local level concerning job training,under-and unemployment.According to our deﬁnition,these workforce invest-ments boards are mandated to engage in collaborative governance.Although public agencies are typically the initiators or instigators of collaborative governance,our deﬁnition requires participation by nonstate stakeholders.Some scholars describe interagency coordination as collaborative governance.Although there is nothing inherently wrong with using the term in this way,much of the literature on collaborativegovernance uses this term to signal a different kind of relationship between public agencies and nonstate stakeholders.Smith (1998,61),for example,argues that collaboratives in-volve ‘‘representation by key interest groups.’’Connick and Innes (2003,180)deﬁne collaborative governance as including ‘‘representatives of all relevant interests.’’Reilly (1998,115)describes collaborative efforts as a type of problem solving that involves the ‘‘shared pursuit of government agencies and concerned citizens.’’We use the term ‘‘stakeholder’’to refer both to the participation of citizens as indi-viduals and to the participation of organized groups.For convenience,we will also here-after use the term ‘‘stakeholder’’to refer to both public agencies and nonstate stakeholders,though we believe that public agencies have a distinctive leadership role in collaborative governance.Our deﬁnition of collaborative governance also sets standards for the type of participation of nonstate stakeholders.We believe that collaborative governance is never merely consultative.3Collaboration implies two-way communication and inﬂuence be-tween agencies and stakeholders and also opportunities for stakeholders to talk with each other.Agencies and stakeholders must meet together in a deliberative and multilateral process.In other words,as described above,the process must be collective .Consultative techniques,such as stakeholder surveys or focus groups,although possibly very useful management tools,are not collaborative in the sense implied here because they do not permit two-way ﬂows of communication or multilateral deliberation.Collaboration also implies that nonstate stakeholders will have real responsibility for policy outcomes.Therefore,we impose the condition that stakeholders must be directly engaged in decision making.This criterion is implicit in much of the collaborative gov-ernance literature.Freeman (1997,22),for example,argues that stakeholders participate ‘‘in all stages of the decisionmaking process.’’The watershed partnerships studied by Leach,Pelkey,and Sabatier (2002,648)make policy and implementation decisions on a range of ongoing water management issues regarding streams,rivers,and watersheds.Ultimate authority may lie with the public agency (as with regulatory negotiation),but stakeholders must directly participate in the decision-making process.Thus,advisory committees may be a form of collaborative governance if their advice is closely linked to decision-making outcomes.In practice (and by design),however,advisory committees are often far removed from actual decision making.We impose the criteria of formal collaboration to distinguish collaborative gover-nance from more casual and conventional forms of agency-interest group interaction.For example,the term collaborative governance might be thought to describe the informal relationships that agencies and interest groups have always cultivated.Surely,interest groups and public agencies have always engaged in two-way ﬂows of inﬂuence.The difference between our deﬁnition of collaborative governance and conventional interest group inﬂuence is that the former implies an explicit and public strategy of organizing this inﬂuence.Walter and Petr (2000,495),for example,describe collaborative governance as a formal activity that ‘‘involves joint activities,joint structures and shared resources,’’and Padilla and Daigle (1998,74)prescribe the development of a ‘‘structured arrangement.’’This formal arrangement implies organization and structure.Decisions in collaborative forums are consensus oriented (Connick and Innes 2003;Seidenfeld 2000).Although public agencies may have the ultimate authority to make 3See Beierle and Long (1999)for an example of collaboration as consultation.Journal of Public Administration Research and Theory546Ansell and Gash Collaborative Governance in Theory and Practice547 a decision,the goal of collaboration is typically to achieve some degree of consensus among stakeholders.We use the term consensus oriented because collaborative forumsoften do not succeed in reaching consensus.However,the premise of meeting together ina deliberative,multilateral,and formal forum is to strive toward consensus or,at least,tostrive to discover areas of agreement.Finally,collaborative governance focuses on public policies and issues.The focuson public issues distinguishes collaborative governance from other forms of consensus decision making,such as alternative dispute resolution or transformative mediation. Although agencies may pursue dispute resolution or mediation to reduce social or politicalconﬂict,these techniques are often used to deal with strictly private conﬂicts.Moreover,public dispute resolution or mediation may be designed merely to resolve private disputes.While acknowledging the ambiguity of the boundary between public and private,we restrict the use of the term‘‘collaborative governance’’to the governance of public affairs.Our deﬁnition of collaborative governance is meant to distinguish collaborative gov-ernance from two alternative patterns of policy making:adversarialism and managerialism (Busenberg1999;Futrell2003;Williams and Matheny1995).By contrast with decisionsmade adversarially,collaborative governance is not a‘‘winner-take-all’’form of interest intermediation.In collaborative governance,stakeholders will often have an adversarial relationship to one another,but the goal is to transform adversarial relationships into more cooperative ones.In adversarial politics,groups may engage in positive-sum bargainingand develop cooperative alliances.However,this cooperation is ad hoc,and adversarial politics does not explicitly seek to transform conﬂict into cooperation.In managerialism,public agencies make decisions unilaterally or through closed de-cision processes,typically relying on agency experts to make decisions(Futrell2003; Williams and Matheny1995).Although managerial agencies may take account of stake-holder perspectives in their decision making and may even go so far as to consult directlywith stakeholders,collaborative governance requires that stakeholders be directly includedin the decision-making process.A number of synonyms for collaborative governance may cause confusion.For ex-ample,‘‘corporatism’’is certainly a form of collaborative governance as we deﬁne it. Classic deﬁnitions of corporatism(like Schmitter’s)emphasize tripartite bargaining be-tween peak associations of labor and capital and the state.Typically,these peak associa-tions have a representational monopoly in their sector(they are‘‘encompassing’’).If westart with this narrower deﬁnition of corporatism,collaborative governance is the broader term.Collaborative governance often implies the inclusion of a broader range of stake-holders than corporatism,and the stakeholders often lack a representational monopoly overtheir sector.The term‘‘associational governance’’is sometimes used to refer to the more generic mode of governing with associations,but collaborative governance may not even include formal associations.The Porte Alegre project,for example,is a form of collabo-rative governance that includes individual citizens in budgetary decision making(Fung and Wright2001).Sometimes the term‘‘policy network’’is used to describe more pluralistic forms ofstate-society cooperation.A policy network may include both public agencies and stake-holder groups.Moreover,policy networks typically imply cooperative modes of deliber-ation or decision making among actors within the network.Thus,the terms policy networkand collaborative governance can refer to similar phenomena.However,collaborative governance refers to an explicit and formal strategy of incorporating stakeholders intomultilateral and consensus-oriented decision-making processes.By contrast,the co-operation inherent in policy networks may be informal and remain largely implicit (e.g.,unacknowledged,unstated,nondesigned).Moreover,it may operate through infor-mal patterns of brokerage and shuttle diplomacy rather than through formal multilateral processes.Collaborative governance and public-private partnership can also sometimes refer to the same phenomenon.Public-private partnerships typically require collaboration to func-tion,but their goal is often to achieve coordination rather than to achieve decision-making consensus per se.A public-private partnership may simply represent an agreement between public and private actors to deliver certain services or perform certain tasks.Collective decision making is therefore secondary to the deﬁnition of public-private partnership.By contrast,the institutionalization of a collective decision-making process is central to the deﬁnition of collaborative governance.Finally,a range of terms are often used interchangeably with collaborative gover-nance.Such terms include participatory management,interactive policy making,stake-holder governance,and collaborative management.We prefer the term governance to management because it is broader and encompasses various aspects of the governing process,including planning,policy making,and management.The term collaborative is also more indicative of the deliberative and consensus-oriented approach that we contrast with adversarialism or managerialism than terms like participatory or interactive.A MODEL OF COLLABORATIVE GOVERNANCEArmed with a working deﬁnition of collaborative governance,we collected a wide range of case studies from the literature.We did this in the typical fashion:we systematically reviewed journals across a wide range of disciplines,including specialist journals in public health,education,social welfare,international relations,etc.We also conducted key word electronic searches using a wide variety of search terms,including those described above and many more (e.g.,‘‘comanagement,’’‘‘public participation,’’‘‘alternative dispute res-olution’’).Of course,we also followed up on the literature cited in the cases we discovered.Ultimately,our model is built on an analysis of 137cases.Although international in scope,our search was restricted to literature in English,and thus,American cases are overrepre-sented.Even a cursory examination of our cases also suggests that natural resource man-agement cases are overrepresented.This is not due to any sampling bias on our part but rather reﬂects the importance of collaborative strategies for managing contentious local resource disputes.Most of the studies we reviewed were case studies of an attempt to implement collaborative governance in a particular sector.As you might imagine,the universe of cases we collected was quite diverse and the cases differed in quality,methodology,and intent.Although our deﬁnition was restrictive so as to facilitate comparison of apples with apples,representing this diversity was also one of our goals.We perceived experiments with collaborative governance bubbling up in many different policy sectors,with little sense that they were engaged in a similar governance strategy.Surely,we felt,these diverse experiments could learn from each other.Yet this diversity proved a challenge.Our original intention to treat these cases as a large-N data set subject to quasi-experimental statistical evaluation was not successful.Since it is useful for both scholarsJournal of Public Administration Research and Theory548Ansell and Gash Collaborative Governance in Theory and Practice549 and practitioners to understand how we arrived at our conclusions,we brieﬂy report on the problems we encountered in conducting our meta-analysis.Early attempts at systematic coding were frustrating,and we soon developed an understanding of our dilemma.Although scholars studying collaborative governancehad already made some important theoretical statements,the language used to describewhat was happening was far from standardized.We found ourselves groping toﬁnda common language of description and evaluation even as we were trying to‘‘code’’studies.Add to this challenge a severe problem of‘‘missing data’’—a reﬂection of thehighly varied motivations of the researchers—and we concluded that a quasi-experimental approach was ill advised.Ultimately,we moved toward a meta-analytic strategy that wecall successive approximation.We selected a subset of our cases and used them to developa common‘‘model’’of collaborative governance.4We then randomly selected additional subsets of case studies.The second subset was used to‘‘test’’the model developed in theﬁrst round and then to further‘‘reﬁne’’the model.A third sample of cases was used to testthe second-round model,and so on.The appendix provides a list of the studies evaluated ineach of four successive rounds of evaluation.Successive approximation has the advantage of both reﬁning the conceptual modelwhile providing some of the evaluative‘‘discipline’’of a quasi-experimental study.How-ever,we are under no illusion that this process yielded‘‘the one’’model of collaborative governance.There was a large element of art involved in both specifying and evaluatingour model.As we proceeded,we were overwhelmed by the complexity of the collaborative process.Variables and causal relationships proliferated beyond what we felt would ulti-mately be useful for policy makers and practitioners.Therefore,our model representsa conscious attempt to simplify as much as possible the representation of key variablesand their relationships.This goal of simpliﬁcation led us to stress common and frequentﬁndings across cases.This approach strengthens the generality of ourﬁndings but dis-counts less universal or frequently mentionedﬁndings from the literature.Toward the endof our analysis,we were ourselves in disagreement about how to represent key relations.We used theﬁnal round of case analysis to settle these differences.One other important clariﬁcation needs to be made before we introduce ourﬁndings.Our survey of the cases quickly disabused us of the notion that we could use our analysis to answer the question:‘‘Is collaborative governance more effective than adversarial or managerial governance?’’Very few of the studies we reviewed actually evaluated gover-nance outcomes.This is not to say that the comparison between collaborative,adversarial,and managerial governance is not relevant to these studies.Experiments with collaborative governance were typically driven by earlier failures with adversarial or managerial approaches.But systematic comparisons were rarely explicitly made.What most studiesdid try to do was understand the conditions under which stakeholders acted collaboratively.Did they engage in good faith negotiation?Did they pursue mutual gains?Did they achieve consensus?Were they satisﬁed with the process?In other words,most studies in the collaborative governance literature evaluate‘‘process outcomes’’rather than policy or management outcomes.Figure1provides a visual representation of our centralﬁndings.The model has fourbroad variables—starting conditions,institutional design,leadership,and collaborative4To avoid recreating the wheel,ourﬁrst subset was not randomly selected but included many of the most prominent theoretical statements about collaborative governance.process.Each of these broad variables can be disaggregated into more ﬁne-grained vari-ables.Collaborative process variables are treated as the core of our model,with starting conditions,institutional design,and leadership variables represented as either critical contributions to or context for the collaborative process.Starting conditions set the basic level of trust,conﬂict,and social capital that become resources or liabilities during col-laboration.Institutional design sets the basic ground rules under which collaboration takes place.And,leadership provides essential mediation and facilitation for the collaborative process.The collaborative process itself is highly iterative and nonlinear,and thus,we represent it (with considerable simpliﬁcation)as a cycle.The remainder of the article describes each of these variables in more detail and draws out their implications for a contingency model of collaborative governance.STARTING CONDITIONSThe literature is clear that conditions present at the outset of collaboration can either facilitate or discourage cooperation among stakeholders and between agencies and stake-holders.Imagine two very different starting points.In one,the stakeholders have a history of bitter division over some emotionally charged local issue and have come to regard each other as unscrupulous enemies.In the other,the stakeholders have a shared vision for what they would like to achieve through collaboration and a history of past cooperation and mutual respect.In both cases,collaboration may be difﬁcult,but the ﬁrst case must over-come problems of distrust,disrespect,and outright antagonism.We narrowed the critical starting conditions down to three broad variables:imbalances between the resources orFigure 1A Model of Collaborative GovernanceJournal of Public Administration Research and Theory550。

Circuits in random graphs from local trees to global loops

a r X i v :c o n d -m a t /0407253v 1 [c o n d -m a t .s t a t -m e c h ] 9 J u l 2004Circuits in random graphs:from local trees to global loops Enzo Marinari †,R´e mi Monasson ‡†Dipartimento di Fisica,SMC-INFM and INFN,Universit`a di Roma ”La Sapienza”,P.A.Moro 2,00185Roma,Italy ‡CNRS-Laboratoire de Physique Th´e orique de l’ENS,24rue Lhomond,75005Paris,France Abstract.We compute the number of circuits and of loops with multiple crossings in random regular graphs.We discuss the importance of this issue for the validity of the cavity approach.On the one side we obtain analytic results for the inﬁnite volume limit in agreement with existing exact results.On the other side we implement a counting algorithm,enumerate circuits at ﬁnite N and draw some general conclusions about the ﬁnite N behavior of the circuits.PACS numbers:02.10.Ox,89.75.Hc,05.40.-a 1.Introduction The study of random graphs,initiated more than four decades ago,has been since an issue of major interest in probability theory and in statistical mechanics.Examples of random graphs abound [1],from the original Erd¨o s-Renyi model [2],where edges are chosen independently of each other between pairs of a set of N vertices (with a ﬁxed probability of O (1/N )),to the scale-free graphs with power law degree distribution [3],only introduced in recent times.An interesting and useful distribution is the one that generates random c -regular graphs [4].These are uniformly drawn from the set of all graphs over N vertices,each restricted to have degree c .Random regular graphs can be easily generated when N is large (and c ﬁnite)[5],and an instance of 3-regular graph is symbolized in ﬁgure 1.Around a randomly picked up vertex called root the graph lookslike a regular tree.The probability that there exists a circuit (a self-avoiding closed path)of length L going through the root vanishes when N is sent to inﬁnity and L is kept ﬁnite ‡[4].The purpose of this article is to reach some quantitative understanding of the presence of long circuits in random graphs.Our motivation is at least two-fold.First,improving our knowledge on circuits in random graphs would certainly have positive fall-out on the understanding of equilibrium properties of models of interacting ‡More precisely,this probability asymptotically departs from zero when log N =O (L ).Finite-length loops may be present in the graph,but not in extensive number.Figure1.Structure of a random regular graph with degree c=3.In the vicinity ofa vertex(the root)the graph looks like a(regular)tree attached to the bulk.For anyinteger D,vertices at distance≤D from the root are almost surely distinct when thesize N of the graph goes to inﬁnity.No short loop,but many long(dashed)ones passthrough the root.variables living on these graphs.For instance,frustration in spin systems emerge from the presence of circuits with odd length.The number of these circuits is therefore directly related to the amount of glassiness present in the system at low temperature.From the dynamical point of view too,the properties of models of interacting or communicating agents e.g.routers,...strongly depend on the topological properties of the underlying graph,and particularly upon feedbacks resulting from the presence of circuits.These “practical”incentives,together with purely academic motivations have led to recent studies on the distributions of unicyclic components[6]and cycles[7]in random graphs.Secondly,the absence of short circuits in random graphs or,equivalently,the observation that random graphs essentially exhibit a local tree-like structure is crucial to the analytical treatment of spin models on random graphs with some common techniques,e.g.the replica or cavity methods.These models are characterized by (realistic)strong interactions between spins,in contrast to usual mean-ﬁeld systems, e.g.Curie-Weiss or Sherrington–Kirkpatrick models.Yet,the absence of short-ranged loops in random graphs make them,around any vertex(root),locally similar to a tree surrounded by a remote bulk.Because of that one conjectures that the free-energy of a spin model on a random graph is equal to the one on the tree with self-consistent boundary conditions requiring that appropriate properties(for example the magnetization for the Ising model)are identical on the leaves and at the root vertex [8,9,10].One of the goals of this note is to point out that this procedure`a la Bethe amounts to make assumptions on the large-scale structure of random graphs,i.e.on the distribution of long loops§.§This point has certainly already come to mind to researchers in theﬁeld but it is,at the best of our knowledge,never explicitly mentioned in the literature.We will ﬁrst discuss loops ,and compute their number in the thermodynamic limit by analyzing the partition function of the Ising model.Next we will compute the number of circuits by discussing the n −→0limit of the O (n )ferromagnetic model.For gathering information about the ﬁnite N behavior of the number of loops (or of the loop entropy)we will use an eﬀective counting algorithm.We will end this note with a discussion of our ﬁndings and of the (many)open issues.2.Inﬁnite size limit:mean-ﬁeld approachIn this section,we enumerate long loops in random graphs from the study of associated statistical mechanics models.We will give our ad hoc deﬁnition of a loop in the following section.2.1.Loops with multiple crossingsLet us consider for example Ising spins S i =±1on vertices i =1,...,N of the graph of ﬁgure 1,and ferromagnetic couplings J ij =1onedges (i,j ).To calculate the partition function Z (β)of the Ising model at inverse temperature βon the graph of ﬁgure 1,we consider the leaves of the uncovered local tree i.e.vertices at distance D from the root (in ﬁgure 1the maximum drawn distance is D =2)[11,8,9,12,10,13].At suﬃciently large β,a spontaneous,say,positive magnetization m is expected to be present in the bulk.As a result,the spins attached to the leaves will feel an external ﬁeld H >0.Integrating these spins out will in turn produce an external ﬁeld H ′acting on spins at distance D −1from the root,with [11]H ′=(c −1)2βln 2(e −β+e βcosh 2βH ∗)+c −1c −1 .(2)The critical inverse temperature is the smallest value of βfor which H ∗is non zero i.e.βc =tanh −1(12L M (L )(tanh β)L ,(3)ABlength l 00.511.5e n t r o p y σlength l 00.51e n t r o p y σFigure 2.Entropy σas a function of the length ℓof loops (full curves)and circuits(dashed curves)for even (A )and odd (B )degrees c (for c =3,loops and circuitscoincide).The slope at origin is ln(c −1)for both cases,the smallest loops beingessentially circuits.Black dots,with coordinates ℓ+,σ+identify the longest loops andcircuits,see text.where M (L )is the number of loops of length L that can be drawn on the graph.It is a sensible assumption that this multiplicity exhibits an exponential growth with the graph size,M (L =ℓN )=exp[N σ(ℓ)+o (N )],(4)where ℓis the intensive length of the loops,and σis the entropy of loops having length ℓ.We stress here that ℓ=O (1)corresponds to L =O (N ).Knowledge of the entropy σwill provide us with information about large-scale loops i.e.with lengths of the order of N .Insertion of the above scaling hypothesis for M (L )in the partition function Z ,and use of the Laplace method yield−βf (β)=−ln 2−c 4,σM =(cis obtained when tanhβ>1,that is,for inverse temperatures with an imaginary part equal toπ2,(βH)∗→(βH)∗+i(c−1)π2−ℓ.The right part of the entropy curve is thus the mirror symmetric of the leftpart with respect toℓ=ℓM(ﬁgure2A).This results from a duality between long and short extensive loops.LetΓF be the full loop(all edges occupied,which is allowed for even c).Then,for any loopΓwith lengthℓ<c2−ℓ.Notice that the largest loop isΓF,withlength c2is reached with an inﬁnite slope,andcorresponds to aﬁnite entropyσ+=1σM :intuitively,the frustration coming from theparity of c is less and less important as c increases+.2.2.Loops without crossings:circuitsThe iteration procedure can be applied to calculate the free-energy of other short-range models and then derive the entropies corresponding to large-scale diagrams generated through high temperature expansions.For instance the ferromagnetic O(n)model with n→0gives information on circuits i.e loops with vertices having degree2at most[16].A spin S is submitted to twoﬁelds H1,H2conjugated to the magnetization S· 1n and itssquared value∗.The iteration equations for theseﬁelds readH′1=(c−1)βH12(1+H2)2.Inserting theﬁxed point values for theﬁelds in the expression of the free-energy per spin component,f=12(1+H2)2 −cyields(for an alternative derivation,see[17]),f=−c−2c−2 +c2−ℓ ln 1−2ℓ2(c ln(c−1)−(c−2)ln(c+1)),is reached inℓM=c2(c−2)ln(1−2/c)correspondsto Hamiltonian cycles.Expression(9)coincides with the output of rigorous calculations [2,18],which shows the exactness of the replica symmetric hypothesis for the O(n→0) model[17].Note the similarity of the entropy curves for loops on odd c-regular graphs and circuits(ﬁgure2).In the two cases the slopes at minimal and maximal lengths are respectivelyﬁnite and inﬁnite,see the discussion above.Let c≥3and M(L)be in all the rest of this note the number of circuits of length L in a random,c-regular graph.Forﬁnite L,M(L)is asymptotically Poisson-distributed when N→∞[4],Proba[M(L)=M]=12LMexp −(c−1)LN,M(ℓ) =(c−1)Lare stuck because there are two left connections that both belong to the same site or that belong to two sites that are already connected.To be sure not to introduce any systematic bias in this case we just discard the full graph and restart the procedure from scratch.3.1.An algorithm for circuit enumerationFor enumerating circuits we have implemented and used an algorithm introduced by Johnson[19].The algorithmﬁnds all elementary circuits of a graph.The computer time needed for this task is bounded by O((N+E)(M+1)),where N is the number of vertices of the graph,E the number of edges and M the total number of circuits in the graph:indeed one proves that the time used between the output of two consecutive circuits is bound by O(N+E)(and that this is true also for time elapse before the output of theﬁrst circuit and after the output of the last one).The memory needed by the algorithm is bounded by O(N+E).Let us just sketch the crucial steps of the procedure.Oneﬁrst orders the vertices in some lexicographic sequence,and labels them with integers ranging from0to N−1. The search is started from a root vertex r,in the subgraph induced by r and by vertices after r:one of the crucial performance issues is that all vertices that become roots are the smallest vertex in at least one elementary circuit.The input to the procedure is the adjacency structure A(v)for each vertex v,that represents the graph:it contains u if and only if(v,u)∈E,where E is the set of edges of the graph.We block a vertex v when it is added to a path beginning in r.We build elementary paths starting from r.The vertices of the current trial paths are loaded on a stack.A procedure adds the vertex to the path,if appropriate,and appends the vertex to the stack:the vertex is deleted from the stack when returning from this procedure.The ingenious part of the algorithm is in keeping a vertex blocked as long as possible,to minimize the execution time.This has to be done while keeping the procedure correct: the basic rule that has to be satisﬁed to guarantee that all circuits are found(only once) is that if it exists a path from the vertex v to r that does not intersect the path loaded on the stack,then v has to be free(i.e.it cannot be in a blocked state).One uses a list to keep the information needed to satisfy this constraint while staying time eﬀective.Some details about performances are as follows:on an Intel Xeon2.8GHz processor our implementation takes of the order of0.07seconds forﬁnding all circuits of a N=30 graph(they are O(50000)),2.4s for N=40(O(1.5106)circuits)and80s for N=50 (with O(4107)circuits).In order to test the results of our code we have also implemented a“quick and dirty”backtracking procedure to count Hamiltonian circuits.Since our procedure crucially depends on the quality of the random number generator we have also checked that diﬀerent(high quality)random number generators lead to statistically compatible answers.0 0.050.10.150.20.250.30.35 0 0.2 0.4 0.6 0.8 1σ(l ), c =3lN=∞Figure 3.Circuit entropy σN (ℓ)as a function of ℓfor c =3,and for graph sizesranging from N =10to 64(from bottom to top).The full curve corresponds to theanalytical calculation of equation (9).Data for sizes multiple of 10are made visibleby using a diﬀerent drawing style.3.2.Results and interpretationThanks to our algorithm and implementation we have been able to enumerate of the order of 1014circuits (a large number).For small c values we can study larger graphs (we have analyzed graphs with up to 64vertices in the c =3case and up to 22vertices for c =6,and averaged our results over samples ranging from 1000to 10000random graphs).Typically we ﬁnd for example of the order of 300million circuits on a N =56,c =3graph,one billion circuits on a N =26,c =5graph and 1.5billion circuits on a N =22,c =6graph.For each value of N ,we average over of the order of 10000samples for all the c =3enumerations,and 1000graphs for c >3.In ﬁgure 3we plot the theoretical results obtained in the (replica symmetric)calculation of Section 2.2for c =3,together with results obtained by ﬁnite enumeration on ﬁnite lattices with N vertices.Numerical data from ﬁnite graphs are very slowly approaching the theoretical,inﬁnite volume data.We try in the following to analyze the quality of this asymptotic agreement of the two sets of data.At ﬁrst we know that log M (ℓ) ∼ℓlog(c −1)as ℓ→0where M (ℓ) is the average number of circuits of length L =ℓ·N .With our numerical data we cannot work really close to ℓ=0,since for ﬁnite N we have a value ℓmin that goes to zero as N →∞:ﬁnite size eﬀects appear as a ﬂattening of log M (ℓ) when ℓbecomes very close to the minimum allowed value (see ﬁgure 3).One can easily see by eye that the slope is very similar to the asymptotic slope in the small ℓregion where we are relatively safe from ﬁnite size eﬀects.We have ﬁtted a linear behavior (that is indeed clear in the data)for example for ℓin the range (.13,.19)for c =3.1 1.522.5 33.5 10 20 30 40 50 60 70(σ(l )-σ∞) N , l =0.5Nc=3c=4c=5c=6Figure 4.N times the diﬀerence between the circuit entropy and its asymptotic value,as a function of N for diﬀerent connectivities c .Here ℓ=0.5.-0.9-0.8-0.7-0.6-0.5-0.4-0.3-0.2-0.1 00.1 0.210 20 30 40 50 60 70(σ(l )-σ∞) N , l =1Nc=3c=4c=5c=6Figure 5.Same as in ﬁgure 4but for Hamiltonian circuits i.e.ℓ=1.Using this approach we ﬁnd for c from 3to 6slopes about 20%smaller than the theoretical prediction (on the larger graphs we can study):for c =3we ﬁnd 0.54versus a theoretical log 2∼0.69;for c =4we ﬁnd 0.87versus 1.10;for c =5we ﬁnd 1.12versus1.39;for c =6we ﬁnd 1.31versus 1.61.Finite size eﬀect can be drastically reduced if we compare directly diﬀerent c value (since we are using graphs of a size that is limited by the same criterion for each c value).For example the ratio of the slope of c and c +1is 0.62for c =3versus a theoretical 0.63,0.78versus 0.79for c =4and 0.85versus 0.86for c =5.This really remarkable agreement gives us conﬁdence that we have a good control over ﬁnite size eﬀects.0.1 0.120.140.160.180.2 0.22 0.24 0.260.280.3 10 20 30 40 50 60σ(l ), c =3, l =0.5Nσ∞ = 0.2877best fit Figure 6.Circuit entropy σ(ℓ=0.5)versus N for c =3and best ﬁt to the form (13).Equation (11)tells us that the diﬀerence between the measured circuit entropy σN (ℓ)and the asymptotic value given by formula (9),once multiplied by N ,behaves as(σN (ℓ)−σ∞(ℓ))N =−log N +˜σ(ℓ)(12)for vanishing small values of ℓ,with ˜σ(ℓ)=−log(2ℓ).It is therefore independent of c ,with a logarithmic dependence upon the graph size N .To check how equation (12)applies to ﬁnite values of ℓ,we look ﬁrst in ﬁgure 4at the number of circuits with ℓ=0.5,for diﬀerent values of N and c (we have harvested our most precise data at c =3).Data indeed show only a very weak dependence upon c ,and this dependence becomes weaker with increasing c .Data for c =5are already indistinguishable from the ones for c =6.In ﬁgure 5,we show the same quantity for ℓ=1i.e.for Hamiltonian circuits,that pass through all vertices of the random graph.As far as the scaling with c is concerned ﬁgure 5shows that the scaling of Hamiltonian circuits is excellent already at c =3.We will come back later about the fact that scaling property of Hamiltonian circuits turn out to be very diﬀerent from the ones of all other ﬁnite ℓ,less dense circuits.Inspired by the result obtained for small circuits (11),(12)we look for the following ﬁt for the circuit entropy for ﬁnite values of ℓ,σN (l )=σ∞(l )+c 1log N N.(13)In ﬁgure 6we show our results for c =3,ℓ=0.5.The quality of the best ﬁt to data with sizes N ≥30only is excellent,and is very good agreement with all data with N ≥12.The two parameter ﬁt is clearly superior to power law ﬁts.We ﬁnd that with very good accuracy (surely better than one percent)c 1=−1,0.125 0.130.1350.14 0.145 0.15 0.155 0.16 10 20 30 40 50 60σ(l ), c =3, l =1 (H a m i l t o n i a n c i r c u i t s )Nσ∞ = 0.1438Figure 7.σ(l =1)versus N for c =3.i.e.that even at ﬁnite ℓthe relation (12)gives the correct leading corrections.This result tells us that for all ℓvalues (maybe excluding ℓ=1,see later)we have that the average number of circuits of reduced length ℓequalsM (ℓN ) =(K (ℓ)+o (1))e N σ∞(ℓ)Anyhow,the salient feature of the above standard approach is that it predicts global thermodynamical quantities from local considerations about the graph only.We have added to our exact computation,valid in the N−→∞limit,results from exact enumeration atﬁnite N.Thanks to them we have been able to determine precisely the behavior of the leading corrections to the thermodynamical behavior(at least for circuits withℓ<1:we have found that Hamiltonian circuits have strongerﬁnite size corrections and a peculiarﬁnite N behavior.It would be very interesting to characterize properties or quantities that can adequately be described by a local procedure[23].The question is however well beyond the scope of the present paper,which only shows that large loops are(remarkably) among those ones.AcknowledgmentsWe are grateful to G.Parisi for insights about the validity of replica symmetry for the Ising model with complex temperature.We also thank S.Cocco,A.Montanari for interesting discussions.R.M.thanks the Les Houches summer school and the SMC-INFM Center in Rome for the hospitality in August and September2003respectively.E.M.thanks the“Laboratoire de Physique Th´e orique”of ENS in Paris for a visiting professorship during May-June2004.References[1]S.N.Dorogovtsev,J.F.F.Mendes,Evolution of Networks:From Biological Nets to the Internetand WWW(Oxford University Press,Oxford,UK,2003)[2]S.Janson,T.Luczak,A.Rucinski,Random Graphs(John Wiley and Sons,New York,USA,2000)[3]M.E.J.Newmann,S.H.Strogatz,D.J.Watts,Phys.Rev.E64,026118(2001).[4]N.C.Wormald Models of Random Regular Graphs in Surveys in Combinatorics,edited by J.D.Lamb and D.A.Preece,London Mathematical Society Lecture Note Series276pp.239–298 (Cambridge University Press,Cambridge,UK,1999)[5]A.Rucinski,N.C.Wormald,put.1,169(1992)[6]E.Ben-Naim,P.L.Krapivsky,preprint cond-mat/0403453[7]H.D.Rozenfeld,J.E.Kirk,E.M.Bollt,D.ben-Avraham,preprint cond-mat/0403536[8]C.de Dominicis,Y.Goldschmidt,J.Phys.A22,L775(1989)[9]P.Mottishaw,Europhys.Lett.4,333(1987)[10]I.Kanter,H.Sompolinsky,Phys.Rev.Lett.58,164(1987)[11]D.R.Bowman,K.Levin,Phys.Rev.B25,3438(1982)[12]C.Bachas,C.de Calan,P.M.S.Petropoulos,J.Phys.A27,6121(1994)[13]A.Lefevre,D.S.Dean,Eur.Phys.J.B21,121(2001)[14]G.Parisi,Statistical Field Theory(Addison Wesley,Redwood City,USA,1988)[15]G.Parisi,private communication.[16]P.G.de Gennes Phys.Lett.38A,339(1972)[17]A.Montanari,M.M¨u ller,M.Mezard,Phys.Rev.Lett.92,185509(2004).[18]H.Garmo,Random Structures Algorithms15,43(1999)[19]D.B.Johnson,SIAM put.4,77(1975)[20]D.J.Thouless,Phys.Rev.Lett.56,1082(1986)[21]R.Monasson,J.Phys.A31,515(1998)[22]M.M´e zard,G.Parisi,Eur.Phys.J.B20,217(2001)[23]D.Aldous,A.Bandyopadhyay,preprint(2004).。

结构钢损伤本构关系的研究

收稿日期:2000-02-25.基金项目:国家自然科学基金资助项目(59678030);长安大学青年科技发展基金资助项目.作者简介:郑　宏(1964-),男,博士,副教授,从事钢结构研究.文章编号:1007-4708(2001)04-0469-04结构钢损伤本构关系的研究郑　宏1,　俞茂宏1,　顾　强2(1.西安交通大学力学博士后流动站,西安710049; 2.西安建筑科技大学,西安710055)摘　要:回顾了结构钢损伤模型的发展史,提出了一种新的本构模型——结构钢弹塑性各向异性损伤本构模型。

该模型采用混合强化准则,考虑Bauschinger效应、屈服平台、硬化(软化)效应及损伤和损伤演化影响。

算例分析结果表明本文模型能够客观地反映结构钢在循环荷载作用下的工作性能、适用于进行钢结构及构件在循环荷载作用下弹塑性反应分析。

关键词:钢结构;弹塑性各向异性损伤;本构关系中图分类号:T U390 文献标识码:A1　引言结构钢损伤本构模型是连续介质损伤力学发展20多年来的成果,应用较为广泛的有各向同性弹塑性损伤本构模型和各向异性损伤理论。

L emaitr e和Chabo che继承了Kachanov的有效应力概念,在实验的基础上,建立了各向同性塑性损伤理论[1-3]; Ro usselier[4]考虑的损伤表现为损伤材料的质量密度低于无损材料的质量密度,建立了宏观的体膨胀损伤模型,并按正交法则推导了各向同性本构关系和损伤演化方程。

然而金相学和材料科学的研究表明,多数材料的损伤破坏是由于晶界处的微裂纹和微孔洞的形核、长大引起的,且在一定应力状态下,晶界上微裂纹和微孔洞的发展具有一定的方向性,即存在损伤材料的各向异性。

为了分析材料的正交异性损伤,Sido ro ff等人[5-6]提出了能量等效假设,对受损材料用二阶损伤张量描述其损伤状态,根据正交法则推出损伤材料的弹性应力-应变关系,并由耗散势函数推出损伤演化方程,提出材料损伤后的本构行为与正交异性材料相同,其坐标主轴与主损伤轴相同,并且损伤弹性矩阵不为常数阵,而与空间坐标及加载史有关。

BEC商务英语初级考试历年真题及答案6套

BEC商务英语初级考试历年真题1 The Scientific Approach to RecruitmentWhen it (0) to selecting candidates through interview, more often than not the decision is made within the first five minutes of a meeting.??Yet employers like to (21) themselves that they are being exceptionally thorough in their selection processes. In today’s competitive market place, the (22) of staff in many organizations is fundamental to the company’s success and, as a result , recruiters use all means at their disposal to (23) the best in the field.One method in particular that has (24) in popularity is testing , either psychometric testing, which attempts to define psychological characteristics , or ability￡aptitude testing (25) an organization with an extra way of establishing a candidate’s suitability for a role. It (26) companies to add value by identifying key elements of a position and then testing candidates to ascertain their ability against those identified elements.The employment of psychometric or ability testing as one (27) of the recruitment process may have some merit, but in reality there is no real (28), scientific or otherwise, of the potential future performance of any individual. The answer to this problem is experience in interview techniques and strong definition of the elements of each position to be (29) as the whole recruitment process is based on few real certainties, the instinctive decisions that many employers make, based on a CT and the first five minutes of a meeting, are probably no less valid than any other tool employed in the (30) of recruitment.21.A suggest B convince C advise D believe22.A worth B credit C quality D distinction23.A secure B relies C attain D achieve24.A lifted B enlarged C expanded D risen25.A provides B offers C contributes D gives26.A lets B enables C agrees D admits27. A portion B member C share D component28. A extent B size C amount D measure29.A occupied B met C filled D appointed30 A business B topic C point D affair《The scientific approach to recruitment》，招人的科学方法。

Knuth-Bendix constraint solving is NP-complete

a r X i v :c s /0207068v 1 [c s .L O ] 17 J u l 2002Knuth-Bendix constraint solving is NP-completeKonstantin Korovin and Andrei VoronkovThe University of Manchester{korovin,voronkov }@February 1,2008AbstractWe show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.1Introduction Solving ordering constraints in term algebras with various reduction orders is used in rewriting to prove termination of recursive deﬁnitions and in automated deduction to prune the search space [Comon 1990,Kirchner 1995,Nieuwenhuis 1999].Nieuwenhuis [1999]connects further progress in automated deduction with constraint-based deduction.Two kinds of orders are used in automated deduction:the Knuth-Bendix order [Knuth and Bendix 1970]and various versions of recursive path orders [Dershowitz 1982,Kamin and L´e vy 1980].The Knuth-Bendix order is used in the state-of-the-art theorem provers,for example,E [Schulz 1999],SPASS [Weidenbach,Afshordel,Brahm,Cohrs,Engel,Keen,Theobalt and Topic 1999],Vampire [Riazanov and Voronkov 1999],and Waldmeister [Hillenbrand,Buch,Vogt and L¨o chner 1997].There is extensive literature on solving recursive path ordering constraints (e.g.,[Comon 1990,Jouannaud and Okada 1991,Nieuwenhuis 1993,Narendran,Rusinowitch and Verma 1999]).The decidability of Knuth-Bendix ordering constraints was proved onlyrecently in [Korovin and Voronkov 2000].The algorithm described in that paper shows that the problem belongs to 2-NEXPTIME.It was also shown that the problem is NP-hard by reduction of the solvability of systems of linear Diophantine equations to the solvability of the Knuth-Bendix ordering constraints.In this paper we present a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints,and hence show that the problem is contained in NP for every term algebra with a Knuth-Bendix order.As a consequence,we obtain that the existential ﬁrst-order theory of any term algebra with a Knuth-Bendix order is NP-complete too.Let us note that the problem of solvability of a Knuth-Bendix ordering constraints consisting of a single inequality can be solved in polynomial time [Korovin and Voronkov 2001].This paper is structured as follows.In Section 2we deﬁne the main notions of this paper.In Section 3we introduce the notion of isolated form of constraints and show that every constraint can be eﬀectively transformed into an equivalent disjunction of constraints in isolated form.This transformation is represented as a nondeterministic polynomial-time algorithm computing22PreliminariesK.Korovin and A.Voronkov.KBO constraint solving is NP-compete342PreliminariesK.Korovin and A.Voronkov.KBO constraint solving is NP-compete563Isolated formsK.Korovin and A.Voronkov.KBO constraint solving is NP-compete783Isolated formsK.Korovin and A.Voronkov.KBO constraint solving is NP-compete9103Isolated formsK.Korovin and A.Voronkov.KBO constraint solving is NP-compete11123Isolated formsK.Korovin and A.Voronkov.KBO constraint solving is NP-compete13143Isolated formsK.Korovin and A.Voronkov.KBO constraint solving is NP-compete15164From constraints in isolated form to systems of linear Diophantine inequalitiesK.Korovin and A.Voronkov.KBO constraint solving is NP-compete17184From constraints in isolated form to systems of linear Diophantine inequalitiesK.Korovin and A.Voronkov.KBO constraint solving is NP-compete19205Main results least N(x)valid on a natural number x if and only if there exists at least N diﬀerentterms of the weight x.Proof.If the signatureΣcontains a unary function symbol of the weight0then the number of diﬀerent terms in any weight is either0orω.Therefore we can deﬁne atleast N(x)↔ Q∈P Q∈S G c(x).It remains to consider the case when our signature contains a function symbol of an arity greater than or equal to2,or contain at least two diﬀerent unary function symbols.By Lemma4.4, there exist constants N1and N2such that for any natural number x such that x>N·N1+N2 the number of terms of the weight x is either0or greater than N.Let us denote N·N1+N2 as M and the set{M′|M′≤M∧tnt(N,M′)≥N}as W.By Lemmas4.4,4.7we have atK.Korovin and A.Voronkov.KBO constraint solving is NP-compete21least N(|x1|).In this way we can replace C simp by an arithmetical constraint,so we assume that C simp is empty.Let C triang have the formy1=TA t1∧...∧y n=TA t n.Let Z be the set of all variables occurring in C arith∧C triang.It is not hard to argue thatC arith∧C triang is satisﬁable if and only if the following constraint is satisﬁable:C arith∧|y1|=N|t1|∧...∧|y n|=N|t n|∧ z∈Z atweight(x,y)↔g(x)≻s(y)∧g(y)≻s(x).It is not hard to argue that,for any ground terms r,t equal225Main resultsweight(s k+2(h(y1,h(y2,...,(15)h(y n−1,y n)))),s2n(y0)).It is not hard to argue that(16)Formula(15)holds if and only if|y1|−1+...+|y n|−1+k=|y0|−1.Using(16),we can transform any system D(x1,...,x n)of linear Diophantine equations of the form(14)into a constraint C(y1,...,y n)such that for every tuple of ground terms t1,...,t n, C(t1,...,t n)holds if and only if so does D(|t1|−1,...,|t n|−1).Similar,using a formulagreaterK.Korovin and A.Voronkov.KBO constraint solving is NP-compete23n .Let us take p=m−1and q=n,then we have|r−p/q|<1/n.Therefore using comparison of terms we can compute r with the precision1/n.This implies that comparison of terms for this Knuth–Bendix order is undecidable.2 6Related work and open problemsIn this section we overview previous work on Knuth-Bendix orders,recursive path orders,and extensions of term algebras with various relations.The Knuth-Bendix order was introduced in[Knuth and Bendix1970].Later,Dershowitz [1982]introduced recursive path orders(RPOs)and Kamin and L´e vy[1980]lexicographic path orders(LPOs).A number of results on recursive path orders and solving LPO and RPO ordering constraints are known.However,except for the very general result of[Nieuwenhuis1993]the techniques used for RPO constraints are not directly applicable to Knuth-Bendix orders.We used systems of linear Diophantine inequalities in our decidability proofs.This is not coincidental:Example5.3shows that systems of linear Diophantine inequalities are deﬁnable in the Knuth-Bendix order.Comon and Treinen[1994]proved that LPO constraint solving is NP-hard already for con-straints consisting of a single inequality.In[Korovin and Voronkov2001]we prove that the24REFERENCESREFERENCES2526IndexSymbols=TA (4)=N (4)≻lex (5)≻—Knuth Bendix order (3)≻w (5)∃-deﬁnable (16)⊥ (6)|t|—weight of t (2)≺ (14)Aarithmetical sort (4)Cchained constraint (5)compatible precedence relation (2)constant (2)constraint (4)contents (16)D dependent (7)depth (18)E equivalence (4)equivalent up to f (9)essential size (8)extends (18)F f (2)f-diﬀerence (9)f-height (9)f-term (9)f-variant (9)ﬂat term (5)Ggrounding substitution (5)Iisolated form (7)KKnuth-Bendix order (3)NN—the set of natural numbers (2)Pprecedence relation (2)Qquasi-ﬂat term (12)R row (8)Ssatisﬁability (4)signature (2)simple (7)size (8)solution (5)substitution (5)grounding (5)TTA(Σ) (2)TA+(Σ) (4)term algebra (2)term algebra sort (4)tnt (18)triangle form (7)V validity (4)Ww—weight function (2)weight (2)of function symbol (2)weight function (2)working constraint (8)。

www13_Wisdom in the Social Crowd an Analysis of Quora

Wisdom in the Social Crowd:an Analysis of QuoraGang Wang,Konark Gill,Manish Mohanlal,Haitao Zheng and Ben Y.Zhao Computer Science,UC Santa Barbara,Santa Barbara,CA93106,USA{gangw,konarkgill,manish,htzheng,ravenben}@ABSTRACTEfforts such as Wikipedia have shown the ability of user commu-nities to collect,organize and curate information on the Internet. Recently,a number of question and answer(Q&A)sites have suc-cessfully built large growing knowledge repositories,each driven by a wide range of questions and answers from its users commu-nity.While sites like Yahoo Answers have stalled and begun to shrink,one site still going strong is Quora,a rapidly growing ser-vice that augments a regular Q&A system with social links between users.Despite its success,however,little is known about what drives Quora’s growth,and how it continues to connect visitors and experts to the right questions as it grows.In this paper,we present results of a detailed analysis of Quora using measurements.We shed light on the impact of three different connection networks(or graphs)inside Quora,a graph connect-ing topics to users,a social graph connecting users,and a graph connecting related questions.Our results show that heterogeneity in the user and question graphs are signiﬁcant contributors to the quality of Quora’s knowledge base.One drives the attention and activity of users,and the other directs them to a small set of popu-lar and interesting questions.Categories and Subject DescriptorsH.3.5[Information Storage and Retrieval]:Online Information Services-Web-based services;J.4[Computer Applications]:So-cial and Behavioral SciencesGeneral TermsMeasurement,Management,DesignKeywordsQ&A System,Online Social Networks,Graphs1.INTRODUCTIONThe Internet is a maelstrom of information,most of it real,and much of it false.Efforts such as Wikipedia have shown that col-lectively,Internet users possess much knowledge on a wide range of subjects,knowledge that can be collated and curated to form valuable information repositories.In the last few years,commu-nity question-and-answer(Q&A)sites have provided a new way for users to crowdsource the search for speciﬁc detailed informa-Copyright is held by the International World Wide Web Conference Committee(IW3C2).IW3C2reserves the right to provide a hyperlinkto the author’s site if the Material is used in electronic media.WWW2013,May13–17,2013,Rio de Janeiro,Brazil.ACM978-1-4503-2035-1/13/05.tion,much of which involves gettingﬁrst-hand answers of speciﬁc questions from domain experts.While these sites have exploded in popularity,their growth has come at a cost.For example,theﬁrst and still largest of these sites, Yahoo Answers,is showing clear signs of stalling user growth and stagnation,with trafﬁc dropping23%in a span of four months in 2011[23].In addition,the Google Answers service launched in 2001was already shut down by2006.Why is this the case?One of the prevailing opinions is that as sites grow,a vast number of low-value questions overwhelm the system and make it extremely difﬁcult for users toﬁnd useful or interesting content.For example, ridiculous questions and answers are so prevalent on Yahoo An-swers that a quick Google search for“Yahoo Answers Fail”turns up more than8million results,most of which are sites or blogs dedicated to documenting them.Bucking the trend thus far is Quora,an innovative Q&A site with a rapidly growing user community that differs from its competitors by integrating a social network into its basic structure.Various esti-mates of user growth include numbers such as150%growth in one month,and nearly900%growth in one year[23].Despite its short history(Quora exited beta status in January2010),Quora seems to have achieved where its competitors have failed,i.e.successfully drawing the participation of both a rapidly growing user population and speciﬁc domain experts that generate invaluable content in re-sponse to questions.For example,founders of Instagram and Yelp answered questions about their companies,Stephen Fry and Ash-ton Kutcher answered questions about actors,and domain-speciﬁc answers come from experts such as Navy Seals sharpshooters and San Quentin inmates.So how does Quora succeed in directing the attention of its users to the appropriate content,either to questions they are uniquely qualiﬁed to answer,or to entertaining or informative answers of interest?This is a difﬁcult question to answer,given Quora’s own lack of transparency on its inner workings.While it is public knowl-edge that Quora differs from its competitors in its use of social networks and real identities,few additional details or quantitative measures are known about its operations.A simple search on Quora about how it works produces numerous unanswered questions about Quora’s size,mechanisms,algorithms,and user behavior.In this paper,we perform a detailed measurement study of Quora, and use our analyses to shed light on how its internal structures con-tribute to its success.To highlight key results,we use comparisons against Stack Overﬂow,a popular Q&A site without an integrated social network.We seek to answer several key questions:•What role do traditional question topics play in focusing user attention?How much do followers of a topic contribute to answering its questions?Figure1:Structure of questions,topics and users in Quora.•What impact do super users have on speciﬁc patterns of user activity?Can they generate and focus user attention on indi-vidual questions,thus setting them apart from questions on related topics?•Given the rapid growth of questions on question-and-answer sites,how does Quora help usersﬁnd the most interesting and valuable questions and avoid spammy or low-value ques-tions?What role do the“related questions”feature play? Our analysis reveals interesting details about the operations of Quora.Weﬁnd that while traditional topic-followers generate traf-ﬁc,social relationships help bring a signiﬁcant amount of answers to questions,and generally provide much higher quality answers than strangers.Most surprisingly,weﬁnd that the related-question graph plays a signiﬁcant role in funneling user trafﬁc and attention to key questions on a given topic.It exhibits a power-law structure where the degree of a question correlates strongly with the number of views and answers it receives.Finally,we use graph partition-ing to identify clusters of related questions in the graph,andﬁnd that the large majority of viewers and answers focus on very few questions within each cluster.This further supports our hypothesis that Quora’s social graph and question graph have been extremely effective at focusing user attention and input on a small subset of valuable questions.2.BACKGROUNDQuora is a question and answer site with a fully integrated social network connecting its users.In this section,we introduce Quora, using Stack Overﬂow as a basis for comparison.We then give de-tails on the key Quora graph structures that connect different com-ponents together.Speciﬁcally,we describe three types of graphs in Quora:a social graph connecting users,a user-topic following graph and a related question graph.2.1Quora and Stack OverﬂowQuora.Quora is a question and answer site where users can ask and answer questions and comment on or vote for existing answers. Unlike other Q&A sites where all users exist in a global search space,Quora allows users to follow each other to form a social network.Social connections in Quora are directional like Twitter.A user A can follow userB without explicit permission,and B’s actions(new questions,answers,comments and topics)will appear in A’s activity stream.We say A is B’s follower and B is A’s followee.In addition,users can follow topics they are interested in, and receive updates on questions and answers under this topic. Each Quora user has a proﬁle that displays her bio information, previous questions and answers,followed topics,and social con-nections(followers and followees).Each user has a“Top Stories”WebsiteDataSinceTotalQuestionsTotalTopicsTotalUsersTotalAnswers Stack Overﬂow Jul.2008 3.45M22K 1.3M 6.86M Quora Oct.2009437K56K264K979KTable1:Data Summary.page,which displays updates on recent activities and participated questions of their friends(followees),as well as recent questions under the topic they followed.A small subset of registered users are chosen by Quora to be reviewers and admins,and have the power toﬂag or remove low quality answers and questions.Finally,each Quora question has its own page,which includes a list of its answers and a list of related ers can add new answers,and comment,edit and vote on existing answers.Stack Overﬂow.Stack Overﬂow is another successful Q&A site started in2008.Stack Overﬂow differs from Quora in two main aspects.First,while Quora covers a broad range of general top-ics,Stack Overﬂow focuses speciﬁcally on computer programming questions.Second,users in Stack Overﬂow are fully independent and no social connections exist between users.2.2Graph Structures In QuoraThe internal structure of question-and-answer sites are often a complex mix of questions,answers,question topics,and users.We summarize the relationships between different entities in Figure1. Users can follow individual topics and other users for news and events;questions are connected to other“related”questions,and each question can be tagged with multiple topics.Finally,for each question in the system,there is a user who asked that question(the asker),users who answered that question(answerers),and users who voted on an answer(voters).Quora’s internal structure is dominated by three graphs that act as channels that guide user interest and deliver information to users.er-Topic Graph:Quora users follow different topics,andreceive updates about questions under topics they follow.2.Social Graph:Quora users follow each other to form a Twitter-like social ers receive newsfeed about questionstheir friends participated in.3.Question Graph:Each question has a list of related questionsused by users to browse related questions.The“related”re-lationship is considered symmetric.We believe these three graphs are largely responsible for guiding the attention of Quora users.In this paper,we will perform de-tailed analysis on these graphs to understand how they impact user activities,especially how they help users separate a small subset of interesting questions from the larger number of less interesting questions/answers.3.DATASET AND PRELIMINARY RESULTS Before diving into main analytical results of our work,we be-gin in this section byﬁrst describing our data gathering methodol-ogy and presenting some preliminary results.Here we describe the properties and limitations of our Quora and Stack Overﬂow datasets.We also analyze some high level metrics of the Quora data,while using Stack Overﬂow as a baseline for comparison. 3.1Data CollectionOur analysis relies on two key datasets.A publicly available dataset periodically released by Stack Overﬂow,and a dataset crawled1021031041051061072008-72008-122009-52009-102010-32010-82011-12011-62011-112012-4N u m b e r o f Q u e s t i o n sStack Overflow Quora (Total)Quora (Crawled)Figure 2:Questions growth. 1 10 100 1000 10000 100000 110 100 1000 10000N u m b e r o f T o p i c sNumber of Questions per TopicFigure 3:#of Questions per topic.0 20 40 60 80 100 05 10 15 20C D F (%)Number of Topics per QuestionStack OverflowQuoraFigure 4:#of Topics per question.from Quora that contains multiple groups of data on users,ques-tions,topics and votes.We describe details below.The basic statis-tics of both datasets are shown in Table 1.Stack Overﬂow.Stack Overﬂow periodically releases all of their data to the public.Our site trace was released in August 2012,and covers all activity on Stack Overﬂow between July 2008and July 2012.Quora.We gathered our Quora dataset through web-based crawls between August and early September 2012.We tried to fol-low crawler-etiquette deﬁned in Quora’s robots.txt .Limited portions of data were embedded in Ajax calls.We used FireWatir,an open-source Ruby library,to control a FireFox browser object,simulating clicking and scrolling operations to load the full page.We limited these crawls to 10requests/second to minimize impact on Quora.Since Quora has no predeﬁned topic structures for its questions (questions can have one or more arbitrary topic “labels”),getting the full set of all questions is difﬁcult.We followed the advice from a Quora data scientist [3]and start our question crawls using 120randomly selected questions roughly evenly distributed over 19of the most popular question topics.The crawls follow a BFS pattern through the related questions links for each question.In total,we obtained 437,000+unique questions.Each question page contains the topics associated to the question,a complete list of answers,and the answerers and voters on each answer.As shown in Table 1,this question-based crawl produced 56,000+unique topics,979,000+answers,and 264,000+unique users who either asked or answered a question,or voted on an answer.Our biggest challenge is trying to understand how much of the Quora dataset we were able to gather.The simple answer is we don’t know,since there are no ofﬁcial quantitative measures about Quora available.But we found a post by a Quora reviewer [2]that hinted the question ID (or qid )in Quora is sequentially assigned.Thus we can infer the total number of questions by inspecting the qid of the newly added questions.To validate this statement,we performed several small experiments where we added small bursts of new (meaningful)questions to Quora.Each burst contains 10new questions sent seconds apart,and consistently produced 10se-quential qid’s.We separated experiments by at least 30minutes,and observed increments to the qid consistent with the expected number of new questions in the gap between experiments.Finally,we plotted qid values for all questions found by our crawl and cor-related them with the estimated date of question creation.The re-sult,discussed below,provides further support that this qid can be used as an estimate of total questions in the system.The largest qid from our crawled questions is 761030,leading us to estimate that Quora had roughly 760K questions at the time of our crawl,and our crawl covered roughly 58%of all questions.Note that not all questions remain on the site,as Quora actively deletes spam and re-dundant questions [5].This estimate might provide an upper boundTopic in Quora #of Questions Topic in Stack Overﬂow #of Questions Startups16.3K C#333K Survey Questions 10.3K Java 277K Movies9.7K PHP257K Medicine /Healthcare 9.3K Javascript 242K Food 8.7K Android 211K Facebook 7.4K jquery 207K Music 5.5K iPhone 143K Google 5.4K C++139K Psychology 5.2K 132K Startup Advice5.2K.net125KTable 2:Top 10topics based on number of questions.of actual number of questions,and our coverage of 58%would be a lower bound.We also crawled the user proﬁles for users extracted from the crawled questions.Each user proﬁle contains 6parts:the list of the user’s followers,list of users they follow (followees),their pre-vious answers,their previous questions,their followed topics and boards.Out of the 264K extracted users,we found that roughly 5000(1.9%)proﬁles were no longer available,likely deleted either by Quora or the user.Qid Over Time.Assuming we are correct about the use of qid,we can plot an estimate of the growth of Quora (and Stack Over-ﬂow),by plotting qid against time.Since Quora does not show when a question is posted,we estimate the posting time by the timestamp of its earliest answer.For open questions with no an-swer,we infer the question posting time based on the latest activity timestamp on the question page.Since reading the question does not update this “latest activity”timestamp,this timestamp can esti-mate posting time for unanswered questions.We estimate the total number of questions in Quora for each month by looking at the largest qid of questions posted in that month.For Stack Overﬂow,we use the timestamp for questions creation in the data trace.We see in Figure 2that Stack Overﬂow is an older site with more questions than Quora.We plot two lines for Quora,a black dashed line for the total number of questions estimated by qid ,and the blue dashed line is the number of questions we crawled from each month.Both lines increase smoothly without gaps,suggesting that Quora did not reset qid in the past and the questions we crawled are not biased to a certain time period.Our estimated number of questions in Quora for June 2012is 700K,which is consistent with previously reported estimates [24].As Quora continues to grow,it is clear that helping users easily identify and ﬁnd the most mean-ingful and valuable questions and answers is a growing challenge.3.2Initial AnalysisTopics.Quora is a general Q&A site with a very broad range of topics.We observed 56K topics in our dataset,which is twice more than that of Stack Overﬂow,even though Quora is smaller by20 40 60 80 100100101102103104105106C D F (%)Number of Views per QuestionStack OverflowQuoraFigure 5:#of User views per question.20 40 60 80 100 1 10100C D F (%)Number of Answers per QuestionStack OverflowQuoraFigure 6:#of Answers per question.20 40 60 80 100 110 100 1000C D F (%)Number of Votes per AnswerStack OverflowQuoraFigure 7:#of V otes per answer.0 2040 60 80 100 0.1 1 10 100C D F (%)Best Answer’s #Votes / Average #VotesStack OverflowQuoraFigure 8:V otes for the best answer vs.the average.20 40 60 80 100 110 1001000C D F (%)Number of Questions per UserStack OverflowQuoraFigure 9:#of Questions per user. 020 40 60 80 100 110 1001000C D F (%)Number of Answers per UserStack OverflowQuoraFigure 10:#of Answers per user.question count.Table 2lists the top 10topics with most number of questions in each site.In Quora,the top 10includes topics in var-ious areas including technology,food,entertainment,health,etc.“Startups”is the most popular one which takes 3.7%of the ques-tions.While all topics in Stack Overﬂow are different,they are all related to programming.The most popular topic is “C#,”which represents roughly 10%of all questions.Figure 3plots the distribution of number of questions per topic in Quora in a log-log grid.It shows that for the large majority of topics,each topic contains only a handful of questions,while a few popular topics are responsible for most of all questions.The distribution of number of questions per topic mirrors a power-law distribution.Performing a power-law ﬁtting produces alpha value 2.28with error 0.03.Questions and Answers.In both systems,one question can have multiple topics.Figure 4shows the number of topics per question.Stack Overﬂow requires a minimum of 1topic and a max-imum of 5topics per question,and the results are evenly distributed between 1and 5.Although Quora does not have such requirements,a majority (85%)of questions have no more than 5topics.Very few (<1%)of questions end up with more than 10topics,which might be an attempt to draw more attention to the question.Next,we plot the distribution of views and answers per ques-tion in Figure 5and Figure 6.We are surprised to ﬁnd that the curves from Stack Overﬂow and Quora are nearly identical.Al-though 20%of questions in Quora remain unanswered (10%for Stack Overﬂow),almost all questions got at least 1user view.In addition,99%of questions end up with less than 10answers,and 20%of all Quora questions managed to collect ≥4answers.We use this as a minimum threshold for our later analyses on social factors on system performance.In terms of votes,both Quora and Stack Overﬂow allow users to upvote and downvote answers.Quora makes visible the list of upvoters,but hides downvoters.Downvotes are processed and only contribute to determining the order answers appear in.Thus in our analysis of Quora,we only refer to upvotes and disregard down-votes.In contrast,Stack Overﬂow anonymizes all voters and only displays the accumulated number of votes,which can be negativeif an answer is poorly received.We plot the distribution of votes per answer in Figure 7.There is still a fairly big portion of answers (about 40%for both sites)that received no votes from users.Next,we look at how votes impact the order that answers are displayed.Quora uses a proprietary algorithm [1]to rank the an-swers,where best answers show on the top of the page.In Stack Overﬂow,the question asker can accept one of the answers as the best answer.First,we examine how well votes work to identify the “best answer.”We select questions with at least 2answers,180K or 40%of all questions in Quora and 1.76M or 51%in Stack Over-ﬂow.Figure 8plots the ratio of the best answer’votes over the average votes per answer under this question.We call this as “best answer vote ratio.”Overall,vote count was very effective at iden-tifying the best answers,and the differences between the two sites might be explained by the more concrete (right or wrong)nature of Stack Overﬂow’s questions compared to general questions on Quora.Surprisingly,some of the best answers have less votes than the average answer.5%of Quora questions ranked answers with fewer upvotes on top,likely due to other features used by Quora’s ranking algorithm such as answerer reputation or downvotes.On Stack Overﬂow,7%of the answers chosen by the asker had lower votes than average.Finally,we note that both sites use crowdsourcing to moderate user-generated content.Stack Overﬂow has administrators who ac-tively ﬂag unqualiﬁed questions and close them [4].Roughly 3%of all questions in Stack Overﬂow have been closed,and Figure 11shows the reasons why they were closed.The top two reasons were “not-real,”i.e.ambiguous,vague,incomplete,overly broad or rhetorical,and redundant questions.In contrast,Quora relies on a total of 43admins and 140reviewers chosen from the user population to ﬂag low quality answers and redundant questions [6,7].The number of ﬂagged or removed answers and questions is unknown.While it is unclear whether these reviewers are respon-sible for keeping Quora largely free of fake or scripted accounts (Sybils)[37,39],recent work has shown that human reviewers can be extremely effective at detecting fake or forged content [36].Users Activity.Finally,we compare levels of user activity in Quora and Stack Overﬂow.Figure 9and Figure 10show the20 40 60 80100l i c a t e -t o p i c j e c t i v e -r e a l -l oc a l i ze dC l o s e d Q u e s t i o n s (%)Figure 11:Reasons for deleting questions in Stack Overﬂow.2040 60 80 100110 100 100010000C D F (%)Topics Followed per UserFigure 12:Topics followed per user.22.2 2.4 2.6 2.8 3110102103104105 500550600 650 700A v e r a g e # o f A n s w e r sA v e r a g e # o f V i e w sSorted Topic Bucket By # of FollowersViews AnswersFigure 13:Average views and answers for questions under sorted topic buckets.total number of questions and answers posted by each user.60%of Stack Overﬂow users did not post any questions (or answers),while less than 1%of active users post more than 1000questions (or answers).We observe similar trends in Quora.40%of the users in our dataset did not post any answers,and 70%of the users have not asked any questions,indicating that a small portion of users have contributed most of the content.Summary.Despite their different topics of interest,Quora and Stack Overﬂow share many similarities in distribution of content and activity.A key observation is that given the broad and grow-ing number of topics in Quora,identifying the most interesting and useful content,i.e.separating the wheat from the chaff,is a very difﬁcult problem.Without built-in mechanisms to lead users to use-ful content,the service will overwhelm users with the sheer volume of its content,much like the Internet itself.This is the focus of the rest of our paper,where we will study different Quora mechanisms to understand which,if any,can keep the site useful by consistently guiding users to valuable information.4.THE USER-TOPIC GRAPHQuora allows users to track speciﬁc ﬁelds by following the cor-responding topics,such as “Startups,”“Facebook,”and “Technol-ogy.”This also directly connects users to questions (and associated answers).A question,once created or updated under a topic,will be pushed to the newsfeeds of users who follow the topic.In this section,we model the interaction between Quora users and topics using a user-topic graph ,and examine the impact of such interac-tions on question answering and viewing activities.Speciﬁcally,we seek to understand whether there is a direct correlation between followers of a topic and views and answers to questions,i.e.do highly-followed topics draw a large number of views and answers to their questions?4.1High-level StatisticsWe ﬁrst examine the number of topics followed by each user 1.Figure 12shows the cumulative distribution of the number of top-ics followed per user.We make three key observations.First,the large majority (95%)of users have followed at least 1topic.This is because Quora recommends topics during the sign-up process.Sec-ond,Quora users each tend to follow a moderate number of topics,e.g.more than 50%of users followed at least 10topics,but 97%of users followed no more than 100topics.Finally,a very small portion of users (27or 0.01%)followed more than 1000topics.We manually checked these users and found that they were legitimate accounts,and come from various backgrounds such as CEOs,co-founders,bloggers,students,and were all very active Quora users.1The user-topic interaction is one-way where users can follow mul-tiple topics,but the relation is asymmetric,i.e.topics do not follow users.Topic#of Followers Topic#of Followers Startups 47,084Google 18,867Facebook 25,569Science 17,669Twitter 23,034TechCrunch 13,313Technology21,852Music13,084Entrepreneurship20,661Venture-Capital12,863Table 3:Top 10topics in Quora based on number of followers.Next,we rank the topics by the number of followers.Since each Quora user lists the topics she follows in her proﬁle,we estimate the number of followers by examining user proﬁles in our crawled dataset.Out of 56K topics crawled,35K topics have at least 1fol-lower in our ing these estimates,we list in Table 3the top 10topics with the most followers.Clearly,users were highly biased towards certain topics.For example,“Startups”was fol-lowed by nearly 18%of users,and “Venture-Capital”by 5%of users.More interestingly,when compared to Table 2ranking top-ics by number of questions,only 4topics (“Startups”,“Facebook”,“Google”,and “Music”)are in the top-10of both rankings.This shows that a high level of interest in a topic,i.e.more followers,does not necessarily produce more questions.4.2Impact on Question-related ActivitiesWe now examine whether user interest towards certain topics translates into higher level of activities on questions related to those topics.We examine the correlation between the number of views or answers per question,and the number of followers of each topic.Since the number of topics is large (35K),we bucketize topics based on the number of followers in a log scale.For example,top-ics with number of followers in the range [1,10]are in one bucket,and topics with number of followers within [10,100]are in a sec-ond bucket.We have a total of 5buckets.In each bucket,we com-pute the number of views (answers)per question,averaged over the topics and their questions.Figure 13shows the correlation results for both question views and answers.We observe a strong correlation:questions under topics with more followers tend to have a higher number of average page views and answers.This is intuitive:when a user follows a topic,all questions under the topic and their updates show up on the user’s newsfeed,thus encouraging page views and answers.We verify this intuition by examining for each question the per-centage of answers that came from followers of the question’s topic(s).Unfortunately we could not do the same for question page views,because Quora only reveals the identity of users who answer ques-tions,but not those who browse each question.We focus on ques-tions with some minimum number of user interactions (≥4an-swers),which ﬁlters out all but 87K (20%)questions from our。

专题25 书面表达之概要写作(解析版)备战2021届高考英语二轮复习题型专练(通用版)

专题25 书面表达之概要写作P a r t1题型总览【题型综述】概要写作是一种“阅读+写作”的复合型任务,测试学生的阅读理解、概括归纳和书面表达方面的综合能力。

选材上，提供一篇350词以内的短文，一般以说明文、议论文和记叙文为主，要求考生写出一篇60词左右的内容概要（注意：少于40或多于80词扣两分），而新写的语篇，既要做到在结构、衔接和连贯性等方面与原文保持一致，又要做到简明扼要、意义完整、结构严密和语句通顺。

【答题策略】1.读懂原文，明确篇章结构写概要之前，一定要先通读原文，确定文章的体裁和主题。

在正确把握文章主旨和段落大意后，明确原文的篇章结构。

根据意义划分文中的自然段，意义段的数量对应的就是要点的数量。

注意一个自然段不一定是一个要点，有时几个自然段说明一个要点，有时一个自然段包含数个要点。

2.去次留精，提炼关键信息·明确全文的篇章结构后，就要处理原文的内容，目的是保留主要内容，删除次要内容。

·先找出主题句，同时标注与主题相关的关键词，最后归纳的要点往往是这些词句的同义转述。

·原文描述性的语言、细节性的信息如列举数字和列举的事例等无须在概要中一一列出。

3.归纳要点合理表达明确每个意义段的关键信息后，接下来应用自己的语言准确地表达各意义段的要点。

为避免和原文的句子重复，可利用同义转述和句式转换这两种形式归纳要点。

各要点的词数应根据文中对应内容的篇幅来定，分清主次。

4.句式多样注意过渡在概要中合理使用非谓语、从句和特殊句式等使句式丰富多样，但句子结构不可过长，也不要用太复杂的句子结构。

同时选用适当的过渡衔接词衔接上下文，保证概要部分内容的连贯性。

P a r t2真题感悟【真题详解】【2019·浙江卷】阅读下面短文，根据其内容写一篇60词左右的内容概要。

It’s a really good idea to visit colleges before you apply because their websites can all start to look and sound the same. Nothing will give you the sense of what it will actually be like to live on a college campus(校园) like visiting and seeing for yourself the dorms, classrooms and athletic equipment and, of course, the students. It seems a little crazy once senior year hits to find the time to visit college campuses, and it can also be pricey if the schools you are applying to happen to be more than a car ride away. But keep in mind that you are making a decision about the next four years of your life, and do all the research you can to make sure you are making the right one.There’s no excuse not to visit the schools in your local area. In fact, a lot of college applications even ask if you have visited campus, and obviously, if you live across the country that won’t be as much of a possibility, but if you live nearby, go check it out!If campus visits aren’t going to happen before you apply, at the very least you should find some time between applying and getting your acceptance letters to visit the schools you’d like to attend. It can save you a lot of heartache if you rule out now the things that you don’t like about certain campuses, things that you wouldn’t know unless you actually visit.Now, if time and money are making it impossible, then check out the online college fairs at CollegeWeekLive. It’s a chance to chat online with admissions officers, students, and college counselors (顾问), and it won’t cost you a penny! Y ou can register for its online college fair at . While visiting an online college fair can’t take the place of an actual campus visit, it can be a very useful tool that along with all your other research will help you make an informed decision about which colleges or universities you’d like to attend.____________________________________________________________________________________________ ____________________________________________________________________________________________ ____________________________________________________________________________________________ ____________________________________________________________________________________________ ________【答案】It’s really worthwhile to pay a visit to their desired colleges personally before applying. Undoubtedly, studentsshould visit their local colleges, which may be included in applications. At least, they should visit the school and figure out its real conditions in advance. For students who are short of money and time, registering for the online college fair is a good alternative to help them better understand schools.【分析】本文要求阅读短文，根据其内容写一篇60词左右的内容概要，即用尽可能少的词汇集中展现原材料的主要思想和观点。

augument相关知识

问题：1。

前提"If your premise is established, your conclusions are easily deducible.""如果你的前提成立,那么就很容易推断出你的结论了。

"·论断的前题是本市没有高尔夫场和假日饭店，或是有但不够吸引人。

但这一前提在论断中没有被保障成立。

因为论断没有提供任何有关本市目前旅游设施的资料，这样我们就无法评估建一个高尔夫场等是必要还是浪费。

前提不成立，论断也就不成立。

2。

经济繁荣：The flourish of economy?3。

通货膨胀和贬值：Inflation & devaluation4。

消费水平/购买力：purchasing power经济形势economic situation5。

本地的优势劣势superiority & inferiority6。

参与研究的人群的性别、年龄、职业等特征的分布The distribution of the gender, the age, and the career of the participants in the study.7。

另外论者也没有告诉我们他们是否在采访中采取了措施以保证结果准确，比如采访话题是否会引导孩子谈论父母。

But we are told nothing about the way the poll was conducted and how well it represented the public opinionsAnd whether it guarantees whether it will influence8。

师资情况，学生结构The overall level of the faculty and the students.9。

它涉及到新添设备、运作等环节，这些都会增加开销。

论者没有提供资料证明这部分开销的上涨会小于远程学位帮助降低的开支。

刘氏毫火针改善脑卒中后上肢痉挛性瘫痪的效果及机制

- 79 -[12]何珏，李贺月，徐妍.基于MAPK/ERK 通路探讨清热化瘀汤对子宫内膜异位症的作用机制[J].西部中医药，2021，34（8）：116-119.[13]王雅红，闫亚男，张艳云，等.子宫内膜息肉切除术后血府逐瘀胶囊辅助黄体酮胶囊对子宫内膜、复发的影响及机制分析[J].中国计划生育学杂志，2022，30（11）：2457-2462.[14]王亚瑜，方秀银，尤晓琳.桂枝茯苓汤联合黄体酮胶囊治疗子宫内膜息肉术后临床效果[J].深圳中西医结合杂志，2023，33（5）：36-38.[15]张曾玲.化痰祛瘀法联合黄体酮胶囊治疗子宫内膜息肉术后痰湿瘀结证患者的疗效观察[J].世界中医药，2020，15（7）：1059-1062.（收稿日期：2023-09-02）　（本文编辑：何玉勤）*基金项目：东莞市科技局社会发展科技面上项目（20221800900602）；东莞市卫生健康局周光辉广东省名中医传承工作室项目（粤中医办函[2020]1号）①东莞市松山湖中心医院康复医学科　广东　东莞　523000②东莞市松山湖中心医院功能检查科　广东　东莞　523000③东莞市松山湖中心医院神经内科　广东　东莞　523000通信作者：周光辉刘氏毫火针改善脑卒中后上肢痉挛性瘫痪的效果及机制*谢淦全①　梁智跃①　付晴②　廖仲波①　周锐钧①　张振钊①　胡斌彬③　周光辉①【摘要】　目的：探讨刘氏毫火针改善脑卒中后上肢痉挛性瘫痪的效果及相关机制。

方法：选择2021年 4月—2022年10月东莞市松山湖中心医院康复医学科及神经内科脑卒中后上肢痉挛性瘫痪患者100例，采用随机数字表法分为对照组（n =50）、观察组（n =50）。

对照组给予常规康复治疗，观察组在对照组基础上增加刘氏毫火针治疗。

比较两组治疗第2、4、8周临床效果及治疗前、治疗第2、4、8周Fugl-Meyer 上肢运动量表（FMA-UE）评分、Barthel 指数（BI）评分、美国国立卫生研究院卒中量表（NIHSS）评分、血清总胆固醇/高密度脂蛋白胆固醇（TC/HDL-C）、载脂蛋白B（ApoB）水平。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

a r X i v :m a t h /0507029v 2 [m a t h .A G ] 19 M a y 2006LIMITS OF CHOW GROUPS,AND A NEW CONSTRUCTION OFCHERN-SCHWARTZ-MACPHERSON CLASSESPAOLO ALUFFI Dedicated to Robert MacPherson on the occasion of his 60th birthday Abstract.We deﬁne an ‘enriched’notion of Chow groups for algebraic varieties,agreeing with the conventional notion for complete varieties,but enjoying a func-torial push-forward for arbitrary maps.This tool allows us to glue intersection-theoretic information across elements of a stratiﬁcation of a variety;we illustrate this operation by giving a direct construction of Chern-Schwartz-MacPherson classes of singular varieties,providing a new proof of an old (and long since settled)conjecture of Deligne and Grothendieck.Contents 1.Introduction 12.proChow groups 53.Globalizing local data 84.proCSM classes 115.The natural transformation F ; A ∗146.Proof of Lemma 5.318References 221.Introduction In the remarkable article [Mac74],Robert MacPherson settled aﬃrmatively a con-jecture of Pierre Deligne and Alexandre Grothendieck (see [Sul71]p.168;and [Gro85],note (871),for Grothendieck’s own comments on the genesis of the original conjecture).MacPherson’s theorem states that there is a unique natural transformation from afunctor of constructible functions on compact complex algebraic varieties to homol-ogy,associating to the constant function 11V on a nonsingular variety V the (Poincar´e dual of the)total Chern class of the tangent bundle T V of V .The class corresponding to the constant 11X for an arbitrary compact complex algebraic variety X is therefore a very natural candidate for a notion of Chern class of a possibly singular variety.After MacPherson’s work it was realized that these classes agree,up to Alexander duality,with classes deﬁned earlier by Marie-H´e l`e ne Schwartz ([Sch65a],[Sch65b];and[BS81]).It is common nowadays to name these classes Chern-Schwartz-MacPherson (CSM)classes.MacPherson’s construction may be used to lift the classes to the Chow group A ∗X ,cf.[Ful84],§19.1.7.Several other approaches to CSM classes are known:for example through local polar varieties ([LT81]);characteristic cycles and index formulas for12PAOLO ALUFFIholonomic D-modules([BDK81],[Sab85],[Gin86]);currents and curvature measures([Fu94]).Some of these approaches may be used to extend the deﬁnition of CSMclasses to varieties over arbitrary algebraically closedﬁelds of characteristic zero(see[Ken90]),proving naturality at the level of Chow groups,under proper push-forward. The main goal of this paper is to provide a new construction of CSM classes inthis algebro-geometric setting,independent of previous approaches,and including acomplete proof of the naturality mandated by the Deligne–Grothendieck conjecture.Our approach is very direct:we simply deﬁne an invariant for nonsingular(but possibly noncomplete)varieties,and obtain the CSM class of an arbitrary variety Xas the sum of these invariants,over any decomposition of X asﬁnite disjoint unionof nonsingular subvarieties.The contribution for a nonsingular variety is obtained asChern class of the dual of a bundle of diﬀerential forms with logarithmic poles.The approach is particularly transparent,as the contribution of a nonsingular sub-variety U to the class for X is independent of how singular X is along U.Auxiliaryinvariants,such as the local Euler obstruction or the Chern-Mather class,which arecommon to several of the approaches listed above,play no rˆo le in our construction.Naturality is straightforward,modulo one technical lemma(Lemma5.3;see also Claim6.1)on the behavior of the contributions under push-forward.The classes wedeﬁne must agree with‘standard’CSM classes,because both satisfy the Deligne–Grothendieck prescription.The main new ingredient making our construction possible is the introduction of ‘proChow groups’,as inverse limits of ordinary Chow groups over the system of maps to complete varieties.Thus,an element of the proChow group A∗U is a compatible choice of a class in each complete variety to which U maps.The proChow groupagrees with the conventional Chow group for complete varieties,but is in generalmuch larger for noncomplete varieties.The key feature of proChow groups is that they are functorial with respect toarbitrary maps:this is what allows us to deﬁne a contribution in A∗X from(for example)an open stratum U of X.If i U:U→X is the embedding,there is in general no push-forward i U∗:A∗U→A∗X,while there is a push forward i U∗: A∗U→ A∗X at the level of proChow groups.Given then the choice of a distinguished element{U}in the proChow group of everynonsingular variety U,satisfying suitable compatibility properties,we may deﬁne an element{X}∈ A∗X for arbitrary(that is,possibly singular)varieties by setting{X}= U i U∗{U}for any decomposition X=∐U U of X into disjoint nonsingular subvarieties U.If X is complete,this gives a distinguished element of the ordinary Chow group A∗X of X.Describing this mechanism gluing local intersection-theoretic information into global one is the second main goal of this article.We show(Proposition3.1)that the compatibility required for this deﬁnition reduces to a simple blow-up formula.We then prove(Proposition4.3)that this blow-up formula is satisﬁed by the Chern class of the bundle of diﬀerential forms with logarithmic poles along a divisor at inﬁnity.PRO-CHOW GROUPS AND PRO-CSM CLASSES3 By the mechanism described above we get a distinguished element{X}∈ A∗X for any X,and this is our pro CSM class of a(possibly singular)variety.We should point out that the‘good local data’arising from the bundle of diﬀerential forms with logarithmic poles is in fact the only nontrivial case we know satisfying the compatibility requirement of Proposition3.1.It would be quite interesting to produce other such‘gluable’data;perhaps it would be even more interesting to prove that this is in fact essentially the only such example,as it would provide a further sense in which(pro)CSM classes are truly canonical.The deﬁnition of proCSM classes extends immediately to constructible functions on X,yielding a transformation from the functor F of constructible functions to the proChow functor A∗.Both functors have a push-forward deﬁned for arbitrary (regular)morphisms,and we prove(Theorem5.2)that the transformation is natural with respect to them.That is:denoting by{ϕ}the proCSM class of the constructible functionϕ,we prove that,for an arbitrary morphism of varieties f:X→Y,{f∗(ϕ)}=f∗{ϕ}.If in particular X and Y are complete,and f is proper,all reduces to the more conventional naturality statement and yields a new proof of(the Chowﬂavor of) MacPherson’s theorem.From a technical standpoint,our construction relies on factorization of birational maps([AKMW02]);the fact that this powerful result is relatively recent is the likely reason why the construction presented here was not proposed a long time ago.Also, we rely on MacPherson’s‘graph construction’in the proof of the key Lemma5.3, similarly to MacPherson’s own proof of naturality in[Mac74].The relation between CSM classes and Chern classes of bundles of diﬀerential forms with logarithmic poles is not new:cf.Proposition15.3in[GP02]and Theorem1in [Alu99b].In fact,this relation and MacPherson’s theory may be used to shortcut the paper substantially.Indeed,our deﬁnition of‘good local data’may be recast as follows:for every nonsingular variety U,one may deﬁne the element{U}∈ A∗U by selecting,for each complete variety X containing U,the elementc∗(11U)∈A∗Xobtained by applying MacPherson’s natural transformation to the function that is1 over U,and0outside of U.Both the basic compatibility(Proposition4.3)and the key Lemma5.3follow then from MacPherson’s naturality theorem.Granting these two facts,the material in§5upgrades MacPherson’s natural transformation F→A∗(which is natural with respect to proper morphisms)to a transformation F→ A∗, natural with respect to arbitrary morphisms.More details on this approach may be found in[Alu06],including simple applications(such as a proof of Ehlers’formula for the Chern-Schwartz-MacPherson class of a toric variety).However,working independently of MacPherson’s naturality theorem,as we do in this paper,allows us to discriminate carefully between parts of the construction which may extend in a straightforward way to a more general context,and parts which depend more crucially on(for instance)the characteristic of the groundﬁeld. For example,Proposition4.3turns out to be a purely formal computation,while Lemma5.3is much subtler,and in fact fails in positive characteristic—this distinction is lost if one chooses to take the shortcut sketched above.4PAOLO ALUFFIOur construction depends on canonical resolution of singularities;at the time of this writing,this is only known to hold in characteristic zero.Should resolution of singularities be proved in a more general setting,our construction will extend to that setting.However,characteristic zero is employed more substantially(for example through generic smoothness)in the proof of naturality,and simple examples show that naturality can not be expected to hold in general in positive characteristic.In fact(as J¨o rg Sch¨u rmann pointed out to me),covariance of the push-forward for constructible functions(Theorem5.1)already fails in positive characteristic.Weﬁnd this state of aﬀairs intriguing.The construction of(pro)CSM classes may well extend to positive characteristic,retaining its basic normalization and additivity properties;these‘only’depend on resolution of singularities,as is shown in this note. But the subtler naturality property of these classes cannot carry over,at least within the current understanding of the situation.It is formally possible to extend MacPherson’s construction of CSM classes to arbitrary characteristic,independently of resolution of singularities;for example,this is done in[NA83],§2.5.It would be interesting to establish whether proCSM classes agree with those deﬁned by Navarro Aznar.In the presence of naturality it is easy to see that proCSM classes agree(for complete varieties,and in the Chow group with Q coeﬃcients)with the classes discussed in[Alu05],§5;but these latter also depend on resolution of singularities.Similar comments apply to a class which may be deﬁned in general for hypersurfaces as a twist of Fulton’s Chern class,and is known to agree with the CSM class in characteristic zero(see[Alu99a];both resolution of singularities and naturality are needed in the proof).We believe the local-to-global formalism described in this note(maybe with diﬀer-ent target functors rather than Chow)should have other applications,for example simplifying the treatment of other invariants of singular varieties;this will be ex-plored elsewhere.Clearly pro-ﬂavors of other functors may be constructed similarly to the proChow functor presented here;we chose to concentrate on this example in view of the immediate application to CSM classes.J¨o rg Sch¨u rmann has pointed out that it would be worth analyzing the construction studied here vis-a-vis the rel-ative Grothendieck group of varieties as used in[BSY](particularly in view of the parallel between the criterion for‘good local data’,given here in Proposition3.1, and Franziska Bittner’s description of the relations deﬁning the Grothendieck group, cf.[Bit04]).Also,Jean-Paul Brasselet has suggested that the construction of proCSM classes may provide an alternative proof of the equality of Schwartz and MacPherson classes,that is,the result of[BS81].A substantial part of this work was done while the author was visiting the Institut de Math´e matiques de Luminy and the Max-Planck-Institut f¨u r Mathematik in Bonn, in the summer of2005.I would especially like to thank Jean-Paul Brasselet and Matilde Marcolli,for the hospitality and for stimulating discussions.I also thank J¨o rg Sch¨u rmann for pointing out inaccuracies in an earlier version of this note,and for several clarifying remarks concerning the case of positive characteristic;and Pierre Deligne for comments on an earlier version of this paper.PRO-CHOW GROUPS AND PRO-CSM CLASSES 52.proChow groups2.1.We work over an algebraically closed ﬁeld k ;further restrictions will come into play later (§2.4and ﬀ.,§5.1and ﬀ.).Schemes will be understood to be separated,of ﬁnite type over k .We say that X is complete if it is proper over k .2.2.We denote by A ∗X the conventional Chow group of X ,as deﬁned in [Ful84];A ∗is then a functor from the category of schemes to abelian groups,covariant with respect to proper maps.We begin by deﬁning a functor A∗from schemes to abeliangroups,covariant with respect to arbitrary (regular)morphisms.For any scheme U consider the category U of maps i :U →X iwith X i complete,and morphisms i →j given by commutative diagramsX iπim(i ));that is,U is aﬁltered category.We will say that an embedding i :U ֒→X i is a closure of U if X i is complete and U is a dense open set of X i ;recall that every scheme U has closures ([Nag63]).Lemma 2.1.Closures form a small coﬁnal subcategoryU beany ﬁxed closure of U .Then i extends to a rational map U X i ,resolving the indeterminacies of which produces a diagramˆU ii X iwith ˆj also a closure of U :since i is deﬁned on the whole of U ,resolving its inde-terminacies may be achieved by blowing up a subscheme in the complement of U ,so the inclusion U ⊂U ,then blowing down a subschemeof the blow-up. Applying the (conventional)Chow functor to closures of U gives an inverse system of groups {A ∗X i }i ∈Ob (6PAOLO ALUFFIDeﬁnition2.2.The proChow group of U is the inverse limit of this system:A∗U:=lim←−i∈Ob(U. Proposition2.5.Assume U is nonsingular.•In order to deﬁne an elementα∈ A∗U it suﬃces to assignαi∈A∗X i for good closures i:U֒→X i,satisfying the following compatibility requirement:PRO-CHOW GROUPS AND PRO-CSM CLASSES 7if i :U ֒→X i ,j :U ֒→X j are good closures,and i →j :X iπdd d A ∗UA ∗U ~~~Indeed,we may associate with every subvariety W of U the class [1Asin[AKMW02],this means that the center of the blow-up and the components of X j U are deﬁned (analytically)at each point by subsets of a system of local parameters.8PAOLO ALUFFI3.Globalizing local data3.1.Next we come to the question of deﬁning global invariants on a variety X from local data:for example,from data given on(open)strata U of a stratiﬁcation of X. The functorial proChow group oﬀers a natural way to do this:•Suppose a class{U}∈ A∗U is deﬁned for every nonsingular irreducible vari-ety U;•then we will deﬁne{X}∈ A∗X by{X}:= U i U∗{U},where X is the disjoint union of the varieties U,each U is nonsingular,irre-ducible,and i U:U→X denotes the inclusion.Of course one has to check that this operation is well-deﬁned.We say that the assignment U→{U}for U nonsingular is good local data if this is the case.In this section we identify a condition yielding good local data.3.2.We denote byU→c Uthe assignment of a class to each nonsingular variety U,in a good closureU U will be obtained as the Chern class of a suitable bundle;in this section we are simply interested in whether this assignment deﬁnes good local data.We will use the following notations:•U:a nonsingular irreducible variety;•U U,a divisor with simple normal crossings inU meeting D with normal crossings;•Z:the intersection W∩U;note that W is a good closure of Z(if Z=∅);•π:U:the blow-up ofEFUZU,etc.as above,c VV E+w∗c W Z.Then the assignments cPRO-CHOW GROUPS AND PRO-CSM CLASSES9 For notational convenience we understand c W Z=0if Z=∅.Also note thatU,π∗:A∗U U determine a class{U}in the proChow group of Uby Proposition2.5:it is part of the statement of Proposition3.1that the necessary compatibility is satisﬁed.Proof.If W is disjoint from U then Z=E=∅,and V∼=U;the assumption reduces toc VU,that is,the compatibility requirement in Proposition2.5.Thus the prescription U→cU such that W=V is a good closure of the latter,the formula in the statement of the proposition implies the claimed equality.To prove that the assignment U→{U}deﬁnes good local data,we have to show that if X is any variety,andX=∐αUαis a decomposition of X as aﬁnite disjoint union of nonsingular subvarieties Uαi Uα10PAOLO ALUFFIwhere X I=∩i∈I X i,andνI:X I֒→X is the inclusion.Proof.This follows immediately from the case in which|J|=2,that is(omitting push-forwards):{X∪Y}={X}+{Y}−{X∩Y},which is straightforward from the deﬁnition. The same applies a fortiori for the degrees {X}(as deﬁned in Remark2.3).3.4.The group of constructible functions of a variety X is the group F(X)ofﬁnite integer linear combinations of functions11Z,for Z subvarieties of X,where11Z(p)= 1p∈Z.0p∈ZForϕ∈F(X),we may deﬁne an element{ϕ}∈ A∗Xas follows:ifϕ= Z n Z11Z,we set{ϕ}=n ZνZ∗{Z},ZwhereνZ:Z֒→X is the inclusion.Inclusion-exclusion implies that this deﬁnition is independent of the decomposition ofϕ(if{·}arises from good local data).In good situations,the choice of good local data determines a push-forward for constructible functions,as follows:if f:X→Y is a morphism of algebraic varieties, deﬁnef∗:F(X)→F(Y)by setting,forϕ= Z n Z11Z as above,and p∈Y,f∗(ϕ)(p)= Z n Z {f−1(p)∩Z};again,the independence on the choices follows from inclusion-exclusion.For the local data we will deﬁne in the next section,and in characteristic zero, the right-hand-side in this prescription is easily seen to be constructible as needed (by Lemma5.8);and we will show that the resulting push-forward is covariant with respect to regular maps.The assignmentϕ→{ϕ}will then give a transformation of functorsF; A∗,and the main result in the rest of the paper will be that,for that choice of local data, this is a natural transformation.Specializing to complete varieties,ordinary Chow groups,and proper maps,will recover the standard algebraic version of MacPherson’s natural transformation.4.proCSM classes4.1.We next choose speciﬁc local data,by means of Proposition3.1.Let U be a nonsingular variety,and let i:U֒→U U is a divisor D with normal crossings and nonsingular components D i,i=1,...,r,inUU:=c(Ω1U]∈A∗U (log D)denotes the bundle of diﬀerential1-forms with logarithmic polesalong D.As we will prove,this assignment speciﬁes good local data.We will use the following immediate lemma:Lemma4.2.Letρ◦:E→Z be a proper,smooth,surjective map of nonsingular va-rieties.Let F,W resp.be good closure of E,W,and assume thatρ◦is the restriction of a proper,smooth,surjective mapρ:F→W.E ρ◦FρWThenρ∗c F E=χ·c W Z,whereχis the degree of the top Chern class of the tangent bundle to anyﬁber ofρ. Proof.Let D=W Z,a divisor with normal crossings and nonsingular components by assumption;F E=ρ−1(D)is then also a divisor with simple normal crossings. In this situation,the exact sequence of diﬀerentials on F:0Ω1F0induces an exact sequence0Ω1F(logρ−1(D))0The statement follows immediately from this sequence and the projection formula, sinceρ∗ c(Ω1F|W∨)∩[F] =χ·[W].4.2.Verifying that the assignment speciﬁed above deﬁnes good local data is now a straightforward(but somewhat involved)computation.Proposition4.3.The classes cProof.We adopt the notation in§3.2,and in particular the blow-up diagramFj Ww U and we have to verify thatcV V E +w ∗c W Z .Also recall thatc (Ω1U )V .Theneeded statement then becomesπ∗c (T (1+F ) i (1+ D i )∩[U )U ],under the assumption that W is contained in at least one component of D .This is Lemma 3.8,part (5),in [Alu05].If Z =∅,that is,W is not contained in any component of D ,then the proper transforms D i of D i agree with the inverse images π−1(D i ),for all i .The blow-up V of U along Z admits V V =∪ Di .The projection formula givesπ∗ c (T i (1+ D i )∩[ i (1+D i )∩π∗(c (T V ])since the class of Di is π∗(D i ).By part (2)of Lemma 3.8in [Alu05],this equals 1U )∩[W ]),where d denotes the codimension of W inU is the embedding.Since W meets D with normal crossings,the divisors D i cut out nonsingular divisors on W ,meeting with normal crossings in W ,and whose union is the complement of Z in W .In other words W is a good closure of Z ,and the computation given above yieldsπ∗c U U +(d −1)w ∗c W Z .On the other hand,VV E =c(T(1+F) i(1+ D i)∩[V)V]−c(T i(1+ D i)∩[F] =c(Ti(1+ D i)∩[ i(1+j∗ D i)∩[F];since F is a good closure of E,with complement given by the union of the intersections D i∩F(of class j∗ D i),this shows c V V−j∗c F E.Combining with the formula obtained above,we getc VV E+w∗ ρ∗c F E−(d−1)c W Z .Nowρ:F→W is a projective bundle,hence smooth and proper,withﬁbers P d−1;it restricts to the projective bundle E→Z.Applying Lemma4.2,with χ= c(T P d−1)∩[P d−1]=d,givesρ∗c F E=d c W Z,concluding the proof.4.3.We are ready to deﬁne proCSM classes,and the corresponding transformation F; A∗.Deﬁnition4.4.The proCSM class of a(possibly singular)variety X is the class{X}∈ A∗Xin the proChow group of X,deﬁned by patching the local data deﬁned in§4.1,asexplained in§3.Explicitly,write X=∐αUαin any way as aﬁnite disjoint union of nonsingular sub-varieties Uαi UαFor the second statement,since both {·}andχtop satisfy inclusion-exclusion we only need to check this equality for X compact and nonsingular.By theﬁrst state-ment(and the Poincar´e-Hopf theorem){X}= c(T X)∩[X]=χtop(X)in this case,as needed.4.4.The proCSM class of a constructible functionϕon a variety X,{ϕ},and the push-forward of constructible functions f∗may now be deﬁned as in§3.4.The second statement in Proposition4.5implies that,for compact complex alge-braic varieties and f proper,this deﬁnition of push-forward for constructible functions agrees with the conventional one(as given in[Ful84],§19.1.7).However,covariance properties of the more general push-forward introduced here, and the naturality of the corresponding transformation F; A∗,do not appear to be immediate.We will address these questions in the next section.5.The natural transformation F; A∗5.1.To summarize,we have now deﬁned a notion of proCSM class for possibly noncomplete,possibly singular varieties X,in the proChow group of X:{X}∈ A∗X.This deﬁnition relies on the local-to-global machinery of§3.We have used resolution of singularities,and the factorization theorem of[AKMW02];the deﬁnition of proCSM class can be given in any context in which these tools apply.By contrast,the statement to be proved in this section will use characteristic zero more crucially.Therefore,in the rest of the paper we work over an algebraically closed ﬁeld of characteristic zero.In§3.4we have also proposed a notion of push-forward of constructible functionsf∗:F(X)→F(Y)for any morphism f:X→Y,and a transformationF; A∗.This depends on f∗(11Z)being a constructible function on Y,for any subvariety Z of X;this is easily seen to be the case for the deﬁnition obtained from the data deﬁned in§4,at least in characteristic zero.Theorem5.1(Covariance).Let f:X→Y,g:Y→Z be morphisms of algebraic varieties.Then(g◦f)∗=g∗◦f∗as push-forwards F(X)→F(Z).Theorem5.2(Naturality).The transformation F; A∗is a natural transformation of covariant functors from the category of algebraic varieties over an algebraically closedﬁeld of characteristic zero,with morphisms,to the category of abelian groups.This is the main result of this paper.In view of Proposition4.5,Theorem5.2 shows that there is a natural transformation from F to A∗,and hence to homology, specializing to the total Chern class of the tangent bundle on nonsingular varieties. This recovers Theorem1in[Mac74].The uniqueness of the natural transformation is immediate from resolution of singularities,and it follows that the(image in homology of the)proCSM classes deﬁned in§4agree with the classes constructed by MacPher-son.This also follows more directly from MacPherson’s theorem,arguing essentially as in the proof of Proposition4.5.In order to provide a self-contained treatment of(pro)CSM classes,MacPherson’s theorem will not be used in the proof of Theorems5.1and5.2(MacPherson’s graph construction will be an ingredient in the proof of Lemma5.3).5.2.It is natural to wonder whether the characteristic zero restriction in Theo-rems5.1and5.2is crucial,or whether it is a technical requirement for our approach to the proof.The restriction is in fact necessary:as J¨o rg Sch¨u rmann pointed out to me,the presence in characteristic p>0of´e tale self-covers of A1,such as the Artin-Schreier map x→x p−x,gives a counterexample to covariance.Other simple examples(such as the Frobenius map)indicate that the diﬃculty cannot be cir-cumvented by naive modiﬁcations to the deﬁnition of push-forward of constructible functions.We do not know,even at a conjectural level,how the formalism could be modiﬁed in order to avoid the characteristic zero requirement.In our argument the condition will enter in the proof of Lemma5.3(speciﬁcally,in the key Lemma6.6),and through ‘generic gentleness’.Sch¨u rmann’s example shows that Lemma5.3fails in positive characteristic.5.3.The proofs of Theorems5.1and5.2depend on the following lemma,which at ﬁrst sight would appear to be a harmless generalization of the trivial Lemma4.2.Its proof is on the contrary rather technical,and we postpone it to§6.We state the lemma here,and use it to prove Theorems5.1and5.2in the rest of this section. Lemma5.3.Let f:U→V be a proper,smooth,surjective map of nonsingular varieties over an algebraically closedﬁeld of characteristic zero.Thenf∗{U}=χf·{V},whereχf= {f−1(p)}(for any p∈V).Since by hypothesis theﬁbers f−1(p)are complete and nonsingular,χf equals the degree of the top Chern class of their tangent bundle(by Proposition4.5).5.4.First,we formulate an upgrade of Lemma5.3to a mildly larger class of maps. Deﬁnition 5.4.A morphism f:U→V of nonsingular varieties is gentle if it is smooth and surjective,and further there is a variety U:U,and fU is a divisor with normal crossings and nonsingular components H i;•letting H I denote the intersection∩i∈I H i(so H∅=U:H I→V|HIis proper,smooth,and surjective.Lemma5.5.If f:U→V is gentle,then the numberχf:= {f−1(p)}is independent of p∈V;further,in characteristic zero,f∗{U}=χf·{V}.Proof.By inclusion-exclusion(Proposition3.2):{U}= I(−1)|I|+1i H I∗{H I}and {f−1(p)}= I(−1)|I|+1 {H I∩f.Since each H I maps properly,smoothly,and surjectively onto V,the statements follow from Lemma5.3.5.5.We also single out the following easy properties of‘gentleness’:Lemma5.6.•If f:U→V is gentle,and W⊂V is a nonsingular subvariety, then the restrictionf−1(W)→Wis gentle;•‘Generic gentleness’holds in characteristic zero:if f:X→Y is any mor-phism of varieties,and X is nonsingular,then there exists a nonempty,non-singular open subset V⊂Y such that f restricts to a gentle map U= f−1(V)→V;•If f,g,and g◦f are all gentle:U f Wthenχg◦f=χg·χf.Proof.Theﬁrst statement is clear.The second is straightforward from Nagata’s theorem extending f to a proper map ([Nag63]),embedded resolution of singularities to guarantee the complement is a divisor H with simple normal crossings,and ordinary generic smoothness(Corollary 10.7in[Har77])applied to all intersections of components of H.For the third,let p be any point of W;by theﬁrst statement,the restrictionf p:(g◦f)−1(p)→g−1(p)。