The definition and application of the concept of complexity is, unsurprisingly, complicated. As related to STS and social studies of science and technology, complexity is most useful when applied in tandem with social systems theory and when emphasizing the connectivity and connections between elements. Generally, complexity describes an arrangement of a large number of elements connected in non-simplistic ways, usually also signifying that conditions could be conducive to something "interesting" happening.

This article covers discussions of complexity by three thinkers:
Niklas Luhmann and Systems Theory
Daniel McShea's Vertical and Horizontal Complexity
Kim Sterelny's Application to Social Structures

Contrast with Emergence
Isabell Stengers clarifies that complexity differs from emergence in that "the notion of emergence implies a physical genesis of the new, whereas the notion of complexity would correspond to a conceptual genesis”.(12) This supports a conceptual, heuristic determining of complexity, rather than attempting to establish a "true" existence of complexity in an absolute way. One way to frame the standards one would use would be to look to Bowker and Star's concepts of classification and standards, the former being a way to divide up entities in a group, and the latter being a set of rules that can be applied across communities or cultures to affect the creation or classification of elements. (See also: Boundary Objects (Jalbert))

Niklas Luhmann and Systems Theory
Because complexity serves as a descriptor applied frequently to systems, it is useful to look first to systems theory to understand characteristics that would be relevant. A system can be defined as a heuristic device to delineate a collection of entities and intra-actions that has some conceptual feature in common, whether as nodes with shared characteristics or as participating elements of a process/activity. Luhmann emphasizes that the differentiation between system and environment is key to a system's existence:

“Systems are oriented by their environment not just occasionally and adaptively, but structurally, and they cannot exist without an environment. They constitute and maintain themselves by creating and maintaining a difference from their environment, and they use their boundaries to regulate this difference. Without difference from an environment, there would not even be self-reference, because difference is the functional premise of self-referential operations. In this sense boundary maintenance is system maintenance.”(16) (Emphasis added)

From this, Luhmann explains that once you can set up a boundary to define the limits of a particular system from its environment, that system can have internal boundaries drawn to carve out subsystems within it, essentially identifying an internal system as distinct from the environment of the larger system:

“As a paradigm, the difference between system and environment forces systems theory to replace the difference between the whole and its parts with a theory of system differentiation. System differentiation is nothing more than the repetition of system formation within systems. Further system/environment differences can be differentiated within systems. The entire system then acquires the function of an “internal environment” for these subsystems, indeed for each subsystem in its own specific way. The system multiplies itself as a multiplicity of system/environment differences." (16) (emphasis added)

This system differentiation increases the complexity of the system:

"Therefore system differentiation is a process of increasing complexity that greatly affects what can be observed as the unity of the entire system. In part, the meaning of differentiation can be viewed as a unity, as a unitas multiplex. In a certain way, difference holds what is differentiated together; it is different and not indifferent.” (16) (emphasis added)

Luhmann's definition of complexity follows:
"we will call an interconnected collection of elements 'complex' when, because of immanent constraints in the elements’ connective capacity, it is no longer possible at any moment to connect every element with every other element. The concept of 'immanent constraint' refers to the internal complexity of the elements, which is not at the system’s disposal, yet which makes possible their 'capacity for unity.' In this respect, complexity is a self-conditioning state of affairs: the fact that elements must already be constituted as complex in order to function as a unity for higher levels of system formation limits their connective capacity and thus reproduces complexity as an unavoidable condition on every higher level of system formation. Leaping ahead, we may hint at the fact that this self-reference of complexity is then 'internalized' as the self-reference of systems.”(24) (emphasis added)

It is also emphasized that a system will never be as complex as the environment surrounding it because in order to differentiate a system, what is within must be more definable and have less noise:
“...the concept of complexity can help to clarify the system/environment difference. Establishing and maintaining the difference between system and environment then becomes the problem, because for each system the environment is more complex than the system itself." (25)

Daniel McShea's Vertical and Horizontal Complexity
Daniel McShea's biologically-based sub-categories identify two binary distinctions that allow for four combinations of complexity. A third possible binary allows for even more possible combinations.

The two starting dichotomies are "object vs. process" and "hierarchical vs. nonhierarchical":

“Even narrowly defined, complexity is still a compound term; it is composed of four distinct types, based on two dichotomies: object versus process, and hierarchical versus nonhierarchical structure. The four possible combinations of these terms generate the four types: (1) Nonhierarchical object complexity; (2) nonhierarchical process complexity; (3) hierarchical object complexity; and (4) hierarchical process complexity." (479)

McShea clarifies the distinction between objects and processes:
"Objects and Processes– Object complexity refers to the number of different physical parts in a system, and process complexity to the number of different interactions among them. For processes, a collision between two billiard balls is simple, whereas an avalanche is complex. Parts do the interacting, but the interactions can be considered on their own, independent of the parts. Indeed, there is no necessary correlation; one part may participate in essentially one (major) interaction, as does a heart, or many, as does a liver.” (479)

An example of (4) - hierarchical process complexity would be an army brigade:
“An army chain of command is such a hierarchy, with the highest ranking officers issuing the most general orders, causing the lower ranks to give more specific orders. Likewise, development is (partly) a causal hierarchy”. (479)

A possible third dichotomy is suggested by McShea to distinguish the above types of complexity from types with "configurational complexity":
“Configurational Complexity – A third dichotomy could be recognized also, differentiation versus configuration. The four types of complexity above are differentiational. Configurational complexity is irregularity of arrangement of parts and interactions, independent of their differentiation.” (480)

Kim Sterelny's Application to Social Structures
Kim Sterelny applies McShea's biologically-originated complexity types to social structure complexity:

“In McShea’s framework, we measure complexity in two dimensions. Social groups are hierarchically structured: individuals are embedded in families, extended families, sometimes in clans or villages as well as tribes and in tribal alliances. Hence, one dimension (‘vertical complexity’) measures the depth of the hierarchical organization an agent experiences. Another dimension ‘horizontal complexity’ measures size and differentiation at a level. As Dunbar has emphasized, numbers matter, in part because the number of relationships in a group grows much faster than group size itself (very much faster, if every member of a group interacts significantly with every other member)." (375)

This ties back to Luhmann's emphasis on interconnection being essential to complexity, and to McShea's distinction between "object" and "process" complexity.

Sterelny relates agents, difference, complexity, and (social) environments in slightly different but compatible ways to other thinkers. Specifically, difference between agents generates more complexity in the social world (environment) surrounding the agent:

"But differentiation matters too. The more the individual agents differ from one another, the more complex the agent’s social world. These differences may be in expertise, economic role, physical capital, dispositions to cooperate or not and mate choice and life-history strategies. Vertical complexity measures structure between the level of individuals and that of the group as a whole. In a vertically simple environment, the social world consists of just individuals and the group as a whole. Add kin groups, clans and totem groups, economic/ecological teams – for instance, the cooperative whale-hunting groups studied by Alvard (Alvard 2002; Alvard & Nolin 2002) – and the social environment becomes vertically complex. For an agent’s prospects will depend in part on his interactions with these proto-institutions. Thus, the complexity of an agent’s social environment depends both on its horizontal and vertical complexity.” (375)

Bowker, Geoffrey C., Susan Leigh Star. Sorting Things Out: Classification and Its Consequences. Cambridge: MIT Press, 1999.
Emery, Nathan, Nicola Clayton, Chris Frith. Social Intelligence: From Brain to Culture. Oxford: Oxford University Press, 2007.
Luhmann, Niklas. Social Systems. Stanford: Stanford University Press, 1995.
McShea, Daniel W. “Metazoan Complexity and Evolution: Is There a Trend?” Evolution, 1996. 50(2): 477-492.
Sterelny, Kim. “Social intelligence, human intelligence and niche construction” in Social Intelligence, 2007. 375-392.
Stengers, Isabelle. Power and Invention: Situating Science. Trans. Paul Bains. Minneapolis: University of Minnesota Press, 1997.