Draft:Port Graph

Draft article not currently submitted for review. This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit or make changes to this draft, simply click on the "Edit" tab at the top of the window. To be accepted, a draft should: Show the subject qualifies for a Wikipedia article by using multiple sources that meet four criteria. The sources should be (1) reliable (2) secondary (3) independent of the subject (4) talk about the subject in some depth. For some topics, there are alternative criteria. Be written from a neutral point of view Respect copyright and do not plagiarize. Do not copy-paste. It is strongly discouraged to write about either yourself or your business or employer. If you do so, you must declare it. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Last edited by Headbomb (talk | contribs) 4 months ago. (Update) Submit the draft for review!

In theoretical computer science and mathematics, a port graph (also written port-graph) is a generalisation of an ordinary graph in which each node possesses a fixed, explicitly named set of ports — designated attachment points — and in which every edge connects exactly two ports rather than two nodes directly.^[1] Port graphs extend multigraphs by making connection points on nodes first-class entities, enabling a finer-grained description of how components interact.

Port graphs arise naturally when modelling systems whose components interact via specific interfaces: two proteins binding at particular chemical sites, two processes communicating over a named channel, or two sub-proofs connected at a specific logical formula. The structure supports a rich theory of graph rewriting and has been applied in biochemical modelling, proof theory, concurrent programming, and the study of distributed and autonomous systems.^[2]

Informally, a port graph is a graph where nodes have explicit connection points called ports. Edges are undirected and connect exclusively at ports; moreover, two ports may be connected by more than one edge, making port graphs a form of labelled multigraph.^[3] Nodes, ports, and edges may all carry labels drawn from some set of properties — for example, a node may be labelled with a name and a colour, an edge with a status such as active or inactive, and a port with a role such as principal or auxiliary.

Let ${\displaystyle N}$ and ${\displaystyle P}$ be two disjoint sets of node names and port names, respectively. A p-signature over ${\displaystyle N}$ and ${\displaystyle P}$ is a mapping

${\displaystyle \nabla :N\to 2^{P}}$

that associates to each node name a finite set of port names. Without loss of generality one assumes that port names belonging to different node names are disjoint.^[1]

Given a p-signature ∇, a port graph ${\displaystyle G}$ consists of:

• A set of nodes, each assigned a name from ${\displaystyle N}$;
• For each node ${\displaystyle v}$ of name ${\displaystyle n}$, a set of ports ${\displaystyle \nabla (n)}$ attached to ${\displaystyle v}$;
• A port-state mapping assigning optional state information to each port (e.g., active or inactive);
• A set of edges, each of the form ${\displaystyle ((v,p),\,(v',p'))}$ connecting port ${\displaystyle p}$ of node ${\displaystyle v}$ to port ${\displaystyle p'}$ of node ${\displaystyle v'}$.^[4]

A port that is not an endpoint of any edge is called a free port. The set of all free ports constitutes the interface of the port graph. Port graphs with a non-empty interface represent open systems that can be composed with others.

A labelled port graph extends the basic definition by equipping nodes, ports, and edges with arbitrary attribute–value pairs drawn from a given signature. This allows the structure to carry semantic information required for particular applications. For instance, in a biochemical model, a node might carry attributes specifying the name of the protein it represents, its phosphorylation state, and its concentration. In a proof-theoretic setting, nodes carry logical connectives and ports carry formula labels.^[5]

A formal treatment of labelled port graphs was given by Fernández, Kirchner, and Pinaud in 2018, who defined a general framework serving as the basis for graph-based programming and modelling environments.^[5]

The conceptual roots of port graphs lie in interaction nets, a graphical model of computation introduced by the French mathematician Yves Lafont in 1990 as a generalisation of the proof structures of linear logic.^[6] In Lafont's formalism, every node (called an agent) possesses a fixed number of ports arranged into one distinguished principal port and zero or more auxiliary ports; computation proceeds by rewriting pairs of agents connected at their principal ports.

Port graphs proper were subsequently developed as an abstract representation of proteins and protein interaction networks, where two proteins connect via sites of chemical compatibility.^[4] Early work by Fernández, Kirchner, and colleagues at INRIA and King's College London formalised the structure and its accompanying rewriting calculus in the context of biochemical and autonomous systems modelling. This led, around 2009–2012, to the development of the PORGY visual modelling environment, in which port graphs are the primary representational primitive.^[7]

Since then, port graphs have been studied from multiple theoretical perspectives — including their relationship to proof nets, the development of higher-order extensions, and their use as a substrate for strategic graph programming — and have found application in domains ranging from systems biology to social network analysis and financial modelling.^[8]

[[#ref_Note: Interaction nets are a special case of port graphs in which each node has exactly one distinguished principal port, rewriting is binary and deterministic, and the strong confluence property holds. General port graphs relax all of these restrictions.|^]]

Port graphs are most commonly studied in the context of port graph rewriting, a rule-based transformation system that generalises both term rewriting and interaction net rewriting to the setting of arbitrary labelled graphs.

A port graph rewrite rule ${\displaystyle r=(L\Rightarrow R)}$ consists of two port graphs — a left-hand side ${\displaystyle L}$ and a right-hand side ${\displaystyle R}$ — together with an arrow node whose ports specify how the free ports of ${\displaystyle L}$ correspond to those of ${\displaystyle R}$.^[9] To apply the rule to a port graph ${\displaystyle G}$, one finds an injective graph morphism (a match) from ${\displaystyle L}$ into ${\displaystyle G}$, removes the image of ${\displaystyle L}$, and inserts a copy of ${\displaystyle R}$, re-attaching the edges that formerly connected to ${\displaystyle L}$'s interface according to the arrow node's port correspondence.

Rewriting is intrinsically non-deterministic: it may be possible to match ${\displaystyle L}$ in several locations in ${\displaystyle G}$, or to apply different rules to overlapping subgraphs, possibly yielding different results. A port graph on which no rule is applicable is said to be in normal form. Each rule application is a rewriting step; a sequence of rewriting steps constitutes a derivation.

Because port graph rewriting is non-deterministic, a strategy is required to control which rules are applied and where. A strategy language for port graph rewriting must cope with the absence of a canonical root position, a feature that distinguishes graphs from terms.^[9] The strategy languages developed for PORGY include primitives such as:

• AllSuc — advance the position to all immediate successors of current position nodes;
• OneSuc — advance to a randomly chosen immediate successor;
• NextSuc — advance along a designated port (e.g., the principal port of each node);
• SetPos(P′) — explicitly set the position to a named subgraph ${\displaystyle P'}$;
• Property(ρ, G′) — restrict the position to nodes satisfying a logical property ${\displaystyle \rho }$.

The full strategy language includes non-deterministic and probabilistic constructs, enabling the modelling of stochastic systems. A formal small-step operational semantics is given using a labelled transition system on derivation trees.^[9]

A port graph morphism ${\displaystyle f:G\to H}$ (where ${\displaystyle G}$ may contain variable nodes and ports but ${\displaystyle H}$ does not) maps nodes, ports, and edges from ${\displaystyle G}$ to ${\displaystyle H}$ while preserving node names and port names (up to variable instantiation), the attachment of edges to ports, and all attribute–value pairs on nodes, ports, and edges.^[9] The morphism intuitively identifies a subgraph of ${\displaystyle H}$ that matches ${\displaystyle G}$ up to variable occurrences. An injective port graph morphism whose domain has no variables is a matching, and finding a matching is a subgraph isomorphism problem.

Interaction nets, introduced by Lafont in 1990,^[6] are a strict special case of port graphs. In an interaction net, every node (agent) of arity ${\displaystyle n}$ has exactly ${\displaystyle n+1}$ ports: one distinguished principal port and ${\displaystyle n}$ auxiliary ports. Computation takes place only when two agents are connected by their principal ports, forming an active pair (or redex). Each active pair type has a unique interaction rule, ensuring strong confluence: no matter in which order redexes are reduced, the same normal form is reached. This confluence property supports massive parallelism without synchronisation.

Port graphs generalise interaction nets by removing the restrictions on the number of principal ports and on the uniqueness of rules. They can therefore model non-deterministic and concurrent systems that interaction nets, being deterministic, cannot directly represent.^[2]

Proof nets are graph-based representations of proofs in linear logic, introduced by Jean-Yves Girard in 1987. The cut elimination procedure on proof nets can be expressed as a sequence of local graph rewritings. Port graphs provide a natural and more general representational framework that encompasses proof nets: a proof net can be encoded as a port graph, and the normalisation of the proof corresponds to port graph rewriting steps.^[10] Higher-order extensions of port graphs have been proposed to more directly express cut-elimination in intuitionistic logic without an exponential enumeration of cases.^[10]

Port graphs have found applications in several domains:

Biochemical and systems biology modelling

The most prominent application domain is the modelling of biochemical reaction networks, particularly protein interaction networks. Each protein is represented as a node whose ports correspond to binding sites; an edge between two ports models a physical bond between two sites. The dynamics of the network — binding events, conformational changes, phosphorylation — are described as port graph rewrite rules, and a strategy controls which rules are applied and in which order. This approach has been applied to the RAF/MEK/ERK signalling cascade and to AKAP scaffold protein models, among others.^[11]

Distributed and autonomous systems

Port graphs have been used to model distributed resources such as grid infrastructures, where each resource is a node with ports. The absence of global information and the autonomous local behaviour of components are captured by a multiset of port graphs and rewrite rules applied concurrently and non-deterministically.^[4]

Social network analysis

Port graph rewriting has been applied to compare propagation models (e.g., information diffusion, epidemiological spreading) in social networks, where nodes represent actors and edges labelled with port states represent the current status of a relationship.^[8]

Proof theory and logic

Port graphs provide graphical representations of proofs in linear and intuitionistic logic that generalise Girard's proof nets and Lafont's interaction nets. The port graph framework supports a uniform treatment of proof normalisation as graph rewriting.^[10]

Programming language semantics

Port graph rewriting serves as a foundational semantic model for graph-based programming languages, providing both operational semantics (via derivation trees) and a basis for program equivalence and verification.^[5]

The primary software tool for port graph rewriting is PORGY (Port Graph Rewriting), a visual and interactive environment developed jointly by teams at INRIA Bordeaux, the University of Bordeaux, and King's College London, with initial development taking place roughly between 2009 and 2012.^[7] PORGY provides:

• A graphical editor for constructing port graphs and port graph rewrite rules;
• A strategy language interpreter for controlling rule application;
• A derivation tree viewer that records the complete rewriting history, allowing users to navigate forward, backward, and across branching derivations;
• Matching and unification algorithms for finding instances of left-hand sides in the current graph;
• Facilities for tracking and plotting quantitative parameters (e.g., node counts, edge counts) over the derivation history.

PORGY supports a stochastic extension of the strategy language in which rule applications carry probabilities, enabling in silico experiments with different priorities or probabilities of biochemical reaction rules.^[11]

Several extensions of the basic port graph formalism have been studied:

Higher-order port graphs

Fernández and colleagues defined a higher-order extension in which rewrite rules themselves are first-class port graph objects that can be rewritten. This enables reflective systems in which rules create new rules, providing a model of adaptive computation. It also allows a more direct encoding of cut-elimination in intuitionistic logic.^[10]

Attributed hierarchical port graphs (AHP)

An attributed hierarchical variant supports nodes that are themselves port graphs, enabling modular and compositional modelling of complex systems.^[8]

Probabilistic and stochastic port graphs

Extensions with probability distributions over rule applications have been developed to support quantitative modelling of biochemical kinetics and stochastic social processes.

Multiport interaction nets

Mazza (2005) defined multiport interaction nets, extending Lafont's original formalism by allowing multiple principal ports per agent, and showed that the resulting system can encode the full π-calculus, providing a faithful graphical representation of mobile concurrent processes.^[12]

• Fernández, M.; Kirchner, H.; Pinaud, B. (2018). "Labelled Port Graph – A Formal Structure for Models and Computations". Electronic Notes in Theoretical Computer Science. 338. Elsevier: 3–21. doi:10.1016/j.entcs.2018.10.002.
• Pinaud, B.; Melançon, G.; Dubois, J. (2012). "PORGY: a visual graph rewriting environment for complex systems". Computer Graphics Forum. 31 (3pt4): 1265–1274. doi:10.1111/j.1467-8659.2012.03119.x.
• Andrei, O.; Fernández, M.; Kirchner, H.; Pinaud, B. (2019). "Strategy-Driven Exploration for Rule-Based Models of Biochemical Systems with Porgy". Modeling Biomolecular Site Dynamics. Methods in Molecular Biology. Vol. 1945. Humana Press.
• Fernández, M.; Pinaud, B. (2012). "Higher-order port-graph rewriting". Electronic Proceedings in Theoretical Computer Science. 101: 25–37. arXiv:1211.4098. doi:10.4204/EPTCS.101.3.

• Interaction nets
• Graph rewriting
• Proof nets
• Linear logic
• Term rewriting
• Bigraph
• π-calculus
• Kappa calculus

Category:Graph theory Category:Rewriting systems Category:Models of computation Category:Formal methods Category:Proof theory Category:Systems biology Category:Theoretical computer science