Quantifiable integrity for Linked Data on the web

2.1.1. URI, resource and resource representation

Adhering to the Linked Data principles, we use Uniform Resource Identifiers (URIs) [7] as names for things which can be virtual, physical or abstract. The thing that is identified by a URI is also called a resource. A resource’s state may be described by the resource’s representation [21] which is retrieved when the resource’s URI is dereferenced. We define a resource’s representation according to [21]:

When dereferencing a resource’s URI yields a representation, the resource is called an information resource. A resource where no representation can be retrieved is called to a non-information resource. Typically, non-information resources are described along side with information resources in an information resource’s representation. For example,

is a non-information resource identifying Tim Berners-Lee. Dereferencing the URI yields the representation of the corresponding information resource

i.e. the profile card where one might find information on the non-information resource. More formal definitions are provided in Section 2.1.3. As representations of information resources that are available on the Web are commonly referred to as Web documents, the terms document, information resource and information resource representation are used synonymously in the remainder of the paper, similar to [27].

A URI [7] is structured as follows:

Square brackets indicate optional parts. Query and fragment are optional parameters that are included when necessary or desired for the resource to be served as intended. The authority and path identify the address at which the resource is hosted. The scheme determines how the subsequent characters are to be interpreted. For example, a http: scheme denotes that interaction with the resource via the HTTP protocol may be possible.

2.1.2. HTTP

For interacting with a resource or, more specifically, its representation, we use the Hypertext Transfer Protocol (HTTP) [19]. With HTTP, two parties communicate with each other: a client, the requesting party, and the server, the responding party. We use the HTTP POST method to create and the HTTP GET method to retrieve a resource’s representation as specified in [20]. For example, when accessing a URI with HTTP GET, the client initiates the communication with the host server identified from the authority and path of the URI. The server processes the request and responds by serving a representation of the requested resource to the client. The resource is served in a data format that has been negotiated between client and server during the communication. One family of such formats is described by the Resource Description Framework (RDF).

2.1.3. RDF

We create resource representations using graphs expressed according to the Resource Description Framework (RDF) [17]. Formal definitions in the realm of RDF are adopted from and stay close to the definitions of [27].

RDF specifies a graph-based data model: An RDF graph is defined as a set of triples. A triple consists of a subject, predicate, and object. In each position, a URI may identify the associated resource. In subject and object position so-called blank nodes may serve as graph-local identifiers. In object position, so-called literals represent values, e.g. numbers or strings. Literals, blank nodes, and URIs are called RDF terms. RDF terms, triples, and graphs are formally defined as follows:

For example (using CURIEs for prefix abbreviations, # denoting a comment), the RDF graph

indicates that Tim Berners-Lee is a Person. Such representation may, for example, be retrieved upon dereferencing the URI of the profile card, the information resource mentioned in Section 2.1.1.

As described in Section 2.1.1, a non-information resource is typically associated to an information resource. This association is also referred to as correspondence.

For example,

the non-information resource identifying Tim Berners-Lee has the corresponding information resource of

An RDF graph may include URIs that correspond to information resources other than the graph’s corresponding information resource itself. In other words, the graph links to other information resources whose representations, i.e. RDF graphs, may link to more information resources and so on. Thus, a directed graph of interlinked information resources, i.e. “Web documents”, is formed. Such graph is thus referred to as document graph.

To reiterate in other words: The terms document, information resource and information resource representation are used synonymously (as mentioned in Section 2.1.1). This is especially intuitive when considering Web documents. A Web document is an information resource and its representation is the document’s content which in turn comprises the document itself. So when a URI identifies a Web document, that document is retrieved upon dereferencing the URI. Links in that document link to other Web documents, thus forming the document graph.

2.1.4. RDF-star

RDF-star [28] (sometimes also RDF^∗) extends the RDF abstract syntax to support easier modelling of statements about other statements. In particular, RDF-star allows for quoting triples, i.e. referencing without asserting, using additional notation of << triple t >>. For example,

indicating that the profile card includes the statement that Tim Berners-Lee is a Person. At the same time, the “outer” statement does not make an assumption about the truth-value of the quoted statement. It only asserts that the profile card includes such a statement. Whether or not Tim Berners-Lee is actually a Person is not asserted. Quoted triples are referentially opaque (in contrast to reified triples), i.e. the quoted triple is considered one entity instead of a composition of its single terms.

2.5.1. Hubs & authorities

The notion of hubs and authorities have originally been defined in the context of the HITS algorithm [32] for calculating a relevance score for pages and documents on the Web. The definition of hubs, authorities and their corresponding scores are adapted from the original definitions found in [32]:

A document’s hub score is the sum of all the authority scores of documents it points to. Not only does the hub score take the number of referenced documents into account, but it also reflects the degree to which a document references authorities, i.e. other documents that are referenced by other hubs. In other words, highly ranked hubs exhibit a considerable overlap in the sets of documents they link to.

A document’s authority score is the sum of all the hub scores of the documents that point to it. Not only does the authority score take the number of documents referencing the document into account, but it also reflects the degree to which a document is referenced by hubs, i.e. other documents that reference other authorities. In other words, highly ranked authorities exhibit a considerable overlap in the sets of documents that reference them.

2.5.2. PageRank

The PageRank [39] is a score that assesses the popularity of Web pages. The idea of the PageRank can be formulated as “Popular pages link popular pages”. The definition of the PageRank is adapted from its original definition as presented in [39] and its calculation via the power method [4]:

In each iteration the PageRank of each document is updated based the PageRank of documents linking to the document. The random surfer is introduced to solve the drainage of PageRank by sinks, i.e. documents with no out-going links [39]. The random surfer jumps from any document to another document in the graph based on a predefined damping factor d. Additionally, the random surfer jumps from a document without outgoing links to any other document in the document graph, by default with uniform probability.

2.6.1. Watts–Strogatz model

The Watts–Strogatz model [50] generates graphs that exhibit the so-called small-world properties of short average path lengths and high clustering of graph nodes. One representative of such small-world networks are social agent networks [50]. The Watts–Strogatz model is thus used in Section 9.3 to create agent networks based on which agent interaction is modelled in the evaluation simulations.

The small-world networks generated by the Watts–Strogatz model are a type of network whose structural properties, e.g. shortest path length or clustering, lie in between the properties of regular graphs and random graphs. In a regular graph, each node is connected to the same number of other nodes, while in a random graph, each node is randomly connected to other nodes. To achieve such structural middle ground, the model’s graph generation is based on rewiring connections between nodes of an initially regular graph. Dependent on a specified probability, each connection between two nodes is rewired.

To create a network using the Watts–Strogatz model, the number of nodes, their number of connections and the rewiring probability need to be specified. A regular graph is generated with the specified number of nodes where each node is connected to the specified number of other nodes. Then, the rewiring procedure is conducted per connection between two nodes in the graph. The thus created graph can be interpreted as a social network of agents, where the graph nodes represent agents and the connections between nodes represent agent interaction, e.g. being friends or chatting with each other. Using such networks, agent interaction can be modelled.

2.6.2. Basic concepts from Game Theory

We examine the behaviour of agents on the Web that is induced by our proposed approach. To analyse more complex agent behaviour, e.g. when agents interact repeatedly, we take inspiration from the analysis of repeated games in Game Theory. We use this technique in Section 9.1.3 to analyse agent behaviour when there is no obvious answer to how an agent may behave given a specified approach to trust scores. This section summarizes the foundations of repeated games in game theory, based on [42].

Agent behaviour is assumed to be rational with the goal of maximising a favorable payoff in a game. The way agents choose to behave within the rules of the game is defined as a strategy. Each agent has its own set of strategies. A game is thus defined as a set of agents and their set of strategies, i.e. their possibilities to play the game according to the rules. Each combination of strategies across all agents, i.e. a scenario that results from the combination of the agents’ behaviour, is associated with an outcome for each agent. Each agent tries to maximise its payoff (also referred to utility) received by an outcome. The fact that an agent maximises its own payoff exclusively affects the decision making of all other agents. A state where no agent is able to receive a better payoff be deviating from its current strategy, given that the strategies of the others remain unchanged, is called a Nash equilibrium.

An agent’s dominant strategy is a strategy that yields the best outcome for that agent independent of the other agents’ strategies. There exists no incentive for that agent to deviate from its dominant strategy regardless of what other agents decide to do. If for each agent there exists a dominant strategy, the resulting Nash equilibrium is called a Nash equilibrium in dominant strategies.

A common tool to represent agents’ payoffs, in a game of two agents, for each strategy they may choose provides the payoff matrix. Agent 1’s possible strategies are denoted by the rows and agent 2’s possible strategies are denoted by the columns. In each tile, the first element of the tuple denotes the potential payoff for agent 1 and the second element of the tuple denotes the potential payoff for agent 2. As illustrated by Fig. 2, dominant strategies as well as Nash equilibria can be identified by simple inspection.

OPEN IN VIEWER

Fig. 2.

A payoff matrix where agent 1 is indifferent between its strategies A and B, and agent 2 has a dominant strategy D over its other strategy C, resulting in the two Nash equilibria (A,D) and (B,D).

In a game that is played once, called a stage game, all agents choose their strategy once and receive the corresponding outcome. A repeated game is a repetition of a stage game, where outcomes are added up. The agents need to take the impact of their current action on future actions of other players into account. Repeated games can be categorised into finitely repeated games and infinitely repeated games. In a finitely repeated game, the expected payoff of an agent’s strategy is the sum of outcomes in each round. In an infinitely repeated game, the expected payoff of an agent is calculated by discounting future outcomes:

9.1.1. Mathematical modeling of trust scores

Three approaches to trust scores are examined: The first approach produces simple degree-based trust scores. The second approach is based on the PageRank [39]. The third approach is adapting the notion of hubs and authorities of [32]. The approaches to trust scores can be summarized by their motto as follows:

Degree-based approach: “Integrity is trust.”

Degree-based approach When integrity preservation is the only factor influencing trust in information resources, the quantitative measures of resource integrity may be interpreted directly as trust scores. The in-degree of a document is then interpreted as the trustworthiness of the document. The higher the in-degree of a document, the more trustworthy that document is. The in-degree of a document is not affected by the in-degree of referencing documents but only the existence of the reference. Thus, the gravitas of a document is equivalent to the existence of a reference to another document, i.e. it is 1 if a reference exists and 0 if there no reference exists.

PageRank As an alternative use case for the PageRank, [39] explicitly states that the PageRank may be an indicator of the trustworthiness of a web page. The idea is adopted for documents published on the Web with self-verifying representations. The interpretation of the PageRank as a trust score can be formulated as “Highly trusted documents reference highly trusted documents”. When a highly trustworthy document references another document, the gravitas of that document leads to additionally increased trust in the referenced document. Highly trusted documents contribute with their gravitas to the trustworthiness and thus gravitas of other documents. In the PageRank-based approach, the trustworthiness as well as the gravitas of a document is determined by its PageRank.

Recall the definition of the PageRank (Definition 8). From the iterative calculation formula, the converged PageRank r ( u ) of a document u is interpreted as the trustworthiness and r ( u ) deg + ( u ) as the gravitas of document u. The gravitas of a document is reduced the higher the out-degree, i.e. the more other documents are referenced by that document.

The notion of a random surfer and its damping factor d is not directly compatible with the interpretation of the PageRank as a trust score. While for the popularity of a Web page it may be acceptable to assume that an agent randomly jumps to another web page, it is hard to find a reasonable interpretation of the random surfer regarding trust scores. Hence, when interpreting the PageRank as a trust score, the damping factor should specified such that the random surfer is prohibited from jumping to a random document in the graph. Then, the random surfer is only allowed to jump from a sink document to a random document in the graph. Since this is done with uniformly distributed probability, a base value is distributed to all documents in the graph. This can be interpreted as a base trust level that is present in the document graph, even on documents that have no incoming links. This way, the problem of sinks is solved and the PageRank calculation results in reasonable values. Accepting the interpretation of the random surfer as a base trust level, the PageRank may serve as a trust score. The PageRank reflects the trustworthiness of a document and the sum of its gravitas at the same time.

Hubs and authorities Adapting the notion of hubs and authorities of [32], hub score and authority score can be interpreted as trust scores for documents published on the Web with self-verifying representations.

Recall the definition of hubs (Definition 6) and authorities (Definition 7): A document’s hub score is the sum of all the authority scores of information resources it points to. The hub score of a document can be interpreted as to how much it contributes to preserving the integrity of the document graph, receiving more weight from highly ranked authorities. The hub score of a document can hence be interpreted as its gravitas. A document’s authority score is the sum of all the hub scores of the information resources that point to it. The authority score of a document can be interpreted as to how well its integrity is preserved by the document graph, receiving more weight from highly ranked hubs. The authority score of a document can hence be interpreted as its trustworthiness.

Obviously, hub scores and authority scores are coupled: The trustworthiness of a document is determined by the gravitas of documents referencing that document. Inversely, the gravitas of a document is determined by the trustworthiness of other documents referenced by that document.

This interpretation of gravitas may seem counterintuitive at first glance because a document’s own trustworthiness does not seem to influence its gravitas. Yet, the hub score of a document is dependent on the authority score of the referenced documents which in turn is dependent on the hub score of the documents referencing them. The hub score of a document is implicitly dependent on other hubs referencing the same documents. Hence, highly ranked hubs exhibit a considerable overlap in the set of documents they link to. The interdependence of the scores therefore fosters interconnectivity among the documents.

Referencing a lot of documents alone does not automatically make a document a highly ranked hub. It is referencing a lot of documents that other hubs reference as well. Only if a document is well interconnected with the other documents, it is able to aggregate the enough gravitas to contribute considerably to another documents trustworthiness. Similarly, a document referenced by one hub is also not automatically a highly ranked authority. Only if it is referenced by more other hubs, its authority score will increase. [32] describes the behavior of hubs mutatis mutandis as “Hubs pull together authorities and allow to rule out unrelated pages of large in-degree”.

The interpretations of gravitas and trustworthiness based on hubs and authorities can thus be refined as follows: A documents gravitas is dependent its own interconnectedness and the interconnectedness of the documents it links to. A documents trustworthiness is dependent on the interconnectedness of the documents it is linked by.

We assess the suitability of the proposed approaches by formal analysis. In particular, we examine the extend to which the modeling of the trust scores induces agent behaviour that contributes to the integrity of the document graph. We assume that an agent tries to maximise the trustworthiness of its own documents and, to this end, includes or excludes links to other documents in new documents it creates. This includes the assumption of rational agents.

The goal of the analysis to find a strategy for an agent to maximise the trustworthiness of its documents. We first try to find a dominant strategy by formally analysing the calculation formula of each trust score approach. Recall Section 2.6.2: A strategy is called dominant if it defines an optimal behaviour for an agent regardless of the behaviour of other agents. As all the agents have the same action set, and thus same strategies, finding a dominant strategy for an agent results in finding a Nash equilibrium in dominant strategies. In the case that we are not able find a Nash equilibrium in dominant strategies that way, we try to find any Nash equilibrium using a Game Theoretic approach: The iterative interaction of agents is represented as a repeated game where agents may collaborate to achieve an overall better outcome for oneself.

9.1.3. Results

Degree-based approach “Integrity is trust.”

This approach relies fundamentally on Definition 10: Trustworthiness is only based on the incoming references of a document. Because the trust score of a document is not tied to its out-degree, there exists no score-inherent incentive to include outgoing links in a document. This means that there is no score-inherent incentive to reference other agents documents and to contribute to the integrity and trust of the document graph. Yet, from a game theoretic perspective, agents may want to collaborate and reference each others documents to increase the trustworthiness of their documents.

Formal Analysis. An agent can only influence the trustworthiness of its own documents by documents it has created itself as Trustworthiness ( u ) = deg − ( u ) = | U in ( u ) | is based on incoming links to a document. The agent is unable to directly influence the gravitas received from other agents’ documents as the gravitas is constant, Gravitas ( u ) = 1 . This is effectively an incentive for an agent to spam new documents with links to its own documents. Which, in itself is not a bad thing as it effectively contributes to the integrity of those documents. If the application recognises the spam, it may choose to exclude the documents from the calculation of the score for other agents. When other agents reference the “spam” documents, the documents may simply become part of the document graph. However, there is no incentive for agents to link to other agent’s documents based on the definition of the trust scores alone.

OPEN IN VIEWER

Fig. 6.

The payoff matrix of the degree-based example ( n i = 1 ) with n i being the number of existing documents of agent i.

Game Theoretic Assessment. Despite the lack of a score-inherent incentive to contribute to the integrity of the document graph, agents may want to collaborate and mutually reference each others documents to increase the trustworthiness of their documents. Consider the following example of two agents. It suffices to examine a two agent game as a game with more agents would just result in parallel pairwise versions of this game. In a nutshell, the game resembles a tit for tat between two agents. Each agent has already published a document, i.e. agent 1 published document 1 and agent 2 published document 2. Each agent is to publish a new document, i.e. agent 1 publishes document 3 and agent 2 publishes document 4. The agents can choose between the same set of strategies when publishing their documents. Strategy O refers to an agent only referencing its own existing document. Strategy B refers to an agent referencing both existing documents. Figure 6 depicts the contribution of the newly published documents to the trustworthiness of documents 1 and 2, i.e. ( T 1 , T 2 ) , in a payoff matrix. It suffices to look at the minimal example of with one existing and one newly created document as additional existing documents or more newly created documents would only positively contribute to the agents payoffs. Of course, when considering n existing documents, one could image any number of placed links as a valid strategy thereby creating derivatives of the two strategies examined in our example. However, the overall intuition of the argument remains unchanged.

Consider the following case: The new document of agent 1 references the existing documents of agent 1 and 2, i.e. agent 1 chooses strategy B, while the new document of agent 2 only references the existing document of agent 2, i.e. agent 2 chooses strategy O. The resulting payoff is ( 1 , 2 ) . Document 1 receives a contribution to its trustworthiness of 1 from the link of document 3 and document 2 receives a contribution to its trustworthiness of 2 from the links of documents 3 and 4.

Both agents are indifferent between strategies O and B because they receive the same payoff regardless of their own action. Instead, their payoff depends only on the other agent’s strategy. In the stage game, all agents are indifferent regarding their own strategy. Thus, we have no dominant strategy for an agent but found two Nash equilibria ( O , O ) and ( B , B ) .

Considering a repeated game, which corresponds to agents repeatedly adding new resources to the document graph. The agents are able to collaborate to achieve an overall better outcome. In a finitely repeated game, it is best to collaborate to achieve the outcome of ( B , B ) in each period. If one agent deviates, the other agent will also deviate and simply stop referencing the other agents documents. This way, the deviating agent is effectively punished by the other agent. In an infinitely repeated game, the same punishment mechanisms exist Recalling the calculation formula (Definition 9), the expected overall payoff for each agent in the agreement for ( B , B ) in each period is (1) payoff = 2 + 2 d + 2 d 2 + ⋯ = 2 + 2 d d − 1 where d is the discount rate. When agent 1 deviates, its payoff is (2) payoff = 2 + d + d 2 + ⋯ = 2 + d d − 1 because agent 2 will stop referencing agent 1’s documents. Since the payoff when adhering to the agreement is higher for any discount factor d deviating is discouraged. Thus, it is always best to collaborate to achieve an overall better outcome, i.e. a higher trustworthiness of an agent’s own documents. When an agent deviates, the agent is punished by the other agents through isolation.

Implications on Graph Evolution. It is best for agents to mutually reference each others documents such that the trustworthiness of all documents is increased. In a document graph, this translates to simply referencing all documents transitively. This is achieved by including references to all documents with an in-degree of zero in a newly published document.

To achieve the long term best outcome, agents have to check if the other agents adhere to the strategy repeatedly. That is, to check, if the other agents were to reference a particular resource and if they did so. This imposes quite the effort on each agent. Moreover, it might not be desirable or even possible to reference all documents with an in-degree of zero. Agents have to choose which documents to reference with their newly published documents. In this case, enforcement is not so straightforward because agents have to decide if a non-reference of their document is intentionally malicious or just imposed by the limitation of references. There is the possibility of the equilibrium in agent behaviour to collapse, and with it the constructive contributions to the document graph. The degree-based trust scores may become obsolete when every agent references their own document and/or other agents’ documents randomly.

Conclusion. While Degree-based trust scores provide no score-inherent incentive and no dominant strategy for agents to collaborate and connect their documents, the incremental creation of the document graph allows for collaboration incentives to emerge. Degree-based trust scores exhibit the potential to incentivise agents to contribute to the document graph in a constructive manner. Moreover, degree-based trust scores provide the agents with an effective enforcement mechanism: If an agent does not cooperate, the agent is isolated and practically excluded from the agent network. However, limitations exist: Degree-based trust scores suffer from link farming. Although link farming attacks can be detected and the responsible agent isolated, it is an additional consideration for application designers to take into account. Moreover, when only a limited number of references is allowed or practically feasible, the equilibrium in agent behaviour may collapse leaving the construction of the document graph to a more random behaviour of agents. This may render degree-based trust scores obsolete. Hence, degree-based trust scores can serve as the foundation for application design but their limitations as well as the possibility of them becoming obsolete need to be taken into account.

PageRank “Highly trusted documents reference highly trusted documents.”

The trustworthiness of a document is only based on incoming references which can not be influenced by the publishing agent itself (except for link farming). The gravitas of a document is also increased with more incoming links. This provides an trust score inherent incentive for link farming. The gravitas of a document is reduced the higher the document’s out-degree. This means that referencing other documents is discouraged and results in an self-focused agent behaviour. PageRank-based trust scores punish the inclusion of more outgoing links and thus punish contributing to the integrity and trust of the document graph.

Formal Analysis. Recall document u’s Trustworthiness ( u ) = r ( u ) = r u = ∑ v ∈ U in ( u ) r i ( v ) deg + ( v ) after convergence and with the damping factor d = 1 , the sum of Gravitas of documents linking to document v. Also recall document v’s Gravitas ( v ) = r ( v ) deg + ( v ) . An agent is not able to directly influence linkage of other agents’ documents, but can only determine which documents are linked by its own documents. Thus, to maximise the trustworthiness of its own documents, the agent has to maximise the gravitas of its own documents. Then, the agent is encouraged to only link its own documents and not link any additional documents as with increasing deg + ( v ) ⟶ ∞ ⇒ Gravitas ⟶ 0 . Thus, it is a dominant strategy for an agent, to only link its own documents and not link any other agent’s documents as this would “waste” a fraction of the document’s gravitas. This fraction would be attributed to some other agent’s document instead of the agent’s own documents. Consider the following example of the graph adjacency matrices A and B and their corresponding transition probability matrices M A and M B . Note that the transition probability from documents with no outgoing links is uniformly distributed across all documents which is due to the random surfer from the definition of the PageRank (see Section 9.1.1). (3) A = 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 , M A = ( 1 / ( 4 ( 1 / ( 4 1 0 ( 1 / ( 4 ( 1 / ( 4 0 1 ( 1 / ( 4 ( 1 / ( 4 0 0 ( 1 / ( 4 ( 1 / ( 4 0 0 B = 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 , M B = ( 1 / ( 4 ( 1 / ( 4 ( 1 / ( 2 0 ( 1 / ( 4 ( 1 / ( 4 ( 1 / ( 2 1 ( 1 / ( 4 ( 1 / ( 4 0 0 ( 1 / ( 4 ( 1 / ( 4 0 0

With the power method, i.e. r k + 1 = M r k with r 0 an arbitrary initial vector and M the transition probability matrix until convergence, it follows that the PageRank of document 1 is lower in graph B than graph A due to the additional link from document 3 to document 2. So, when documents 1 and 3 belong to the same agent, it would be better for that agent to not include the link from document 3 to 2. We provide the formal proof for this intuition in Appendix A.

The PageRank does not provide an inherent incentive for agents to collaborate and contribute to the document graph in a constructive way. Moreover, it is a dominant strategy to not collaborate. The PageRank is thus not suitable as foundation for designing applications based on trust scores.

Hubs and authorities “Trust is based on the interconnectedness of documents.”

To increase the trustworthiness of a document, it needs to referenced by preferably multiple highly ranked hubs. This way, agents are incentivised to create hubs such that they can increase the trustworthiness of their own documents. Contribution to the integrity and trust of the document graph is thus incentivised when considering hubs and authorities as the foundation of trust scores.

Formal Analysis. Referencing highly ranked hubs leads to a new document becoming a highly ranked hub itself. More formally, [32] shows that the hub score vector h is the principal eigenvector of the hub matrix H = A A T with A being the adjacency matrix of the graph. Moreover, the principal eigenvector h can be approximated using the power method as the unit vector resulting from the convergence of (4) h = ( A A T ) k z with k ⟼ ∞ where k, the number of iterations, and z, the identity vector.

Using the power method, the reasoning behind the definition of hubs (and authorities analogously) becomes apparent. Consider two exemplary graphs and their corresponding adjacency matrices A and B. In the first graph, node 3 and 4 both link to node 1 and 2, while in the second graph node 4 additionally links to node 3. (5) A = 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 , H A = 0 0 0 0 0 0 0 0 0 0 2 2 0 0 2 2 = A A T B = 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 , H B = 0 0 0 0 0 0 0 0 0 0 2 2 0 0 2 3 = B B T

In a hub matrix H, the values on the diagonal H i j ( i = j ) indicate the out-degree of the node, while the other values H i j ( i ≠ j ) indicate the number of nodes commonly linked to by node i and node j. So when using the power method, it becomes intuitive that nodes with a high out-degree as well as a high number of nodes commonly referenced by other nodes exhibit high hub scores.

As an example, consider nodes 3 and 4 and their corresponding rows in the hub matrices. Since both nodes link to the same nodes, i.e. 1 and 2, entries H 34 = H 43 = 2 . Both nodes exhibit an out-degree of 2. In the second graph however, node 4 references node 3, thus having an out-degree of 3. Consider the hub scores of nodes 3 and 4 after the first iteration with an initial z = ( 1 , 1 , 1 , 1 ) T after normalisation: (6) H A z 0 = ( 0 , 0 , 4 , 4 ) T → z 1 = ( 0 , 0 , ( 1 / ( 2 , ( 1 / ( 2 ) T H B z 0 = ( 0 , 0 , 4 , 5 ) T → z 1 = ( 0 , 0 , ( 4 / ( 9 , ( 5 / ( 9 ) T

In the first graph, both nodes exhibit the same hub score due to linking to the same nodes. Quite intuitively, the hub score of node 4 is higher in the second graph than in the first graph due to the higher out-degree. It is also higher than the score of node 3. This illustrates that a node linking to the same set of nodes as another node will have the same hub score as that node. Moreover, a node that links to the same set of nodes as another node and additionally links that note itself, will exhibit a higher hub score than that node. Subsequently, when considering transitivity, a node only needs to reference the particular other node to automatically achieve a higher hub score than that node. Considering the second graph of the example, node 4 only links to node 3 in the graph’s transitive reduction while simultaneously achieving a higher hub score than node 3.

From this reasoning, we conclude the following lemma:

We provide formal proof for Lemma 1 in Appendix B.

Game Theoretic Assessment. In the context of interpreting the hub score as a trust score, it follows from Lemma 1 that it is sufficient to reference existing hubs instead of authorities to achieve a higher hub score than existing hubs on the transitive closure of the document graph. In other words, contribution to the document graph is incentivised, and in particular referencing existing hubs. It follows that all hubs should be referenced to ensure a hub score higher than any existing hub and thus impact on authority score of other documents. Practically, that means referencing all available documents on the transitive closure of the graph, which is achieved by referencing all documents with no incoming links.

When an agent wants to increase the authority score and thus trustworthiness of its own documents, it is best to publish a new document that references many documents, preferably with a high hub score. Even when other agents choose to only reference specific documents, it still remains best for an agent to reference as many documents as possible. This strategy is independent from the behaviour of the other agents and as such a dominant strategy.

Implications on Graph Evolution. The high hub score documents are typically “newer” documents, i.e. documents with an in-degree of zero, that reference many if not all already existing documents. This means, that when a document is added to the document graph, it should reference many high hub score documents to become a hub itself and subsequently a valuable target to reference for new documents. This way, the documents will receive more incoming references as new documents are added, thereby gaining authority score. In turn, documents will slowly loose hub score as new documents are added because they link to more other documents and thus exhibit a relatively higher hub score. As the document graph evolves over time by incremental additions, a document will slowly lose its hub score but gain authority score instead. With each new document referencing a particular document, its gravitas is incrementally transformed into trustworthiness.

Interpreting hub and authority score as trust scores for gravitas and trustworthiness not only imposes a short term incentive to create a hub to increase the trustworthiness of own documents, but also provides a long term incentive to create a hub due to hubs being transformed to authorities as the document graph evolves. With the document graph incrementally growing, the trust scores maintain their meaningfulness. Hub and authority based trust scores incentivise agents to contribute to the document graph in a constructive manner which allows the document graph to evolve without its underlying trust scores becoming obsolete over time.

Even when the number of references for newly published documents is limited, the incentive remains to gain a high hub score. There does not exist an incentive for agents to deviate from their dominant strategy, unlike with degree-based trust scores.

Conclusion. The notions of hubs and authorities and their corresponding scores based [32] are well suited to be interpreted as trust scores in document graphs. Moreover, they provide an inherent incentive and dominant strategy for agents to contribute to the document graph in a constructive fashion keeping the graph and its underlying trust scores intact. Limiting the number of references of new documents does not affect agent behaviour when using hub and authority based trust scores.

Degree-based trust scores can serve as the foundation for application design but their limitations as well as the possibility of them becoming obsolete need to be taken into account. PageRank-based trust scores provide no incentive for agents to collaborate and contribute to the document graph constructively. Thus, they are not suited as the foundation for trust scores. Only Hub and Authority scores are well suited as trust scores. They provide an inherent incentive to contribute to the document graph constructively, while not suffering from any limitation that are present for the other approaches. Based on this assessment, we choose to examine applications that are designed using trust scores based on hubs and authorities.

Let G + denote the transitive closure of the unmodified graph G = ( V , E ) . A new vertex v is added to the graph. Let G ′ = ( V ′ , E ′ ) with V ′ = V ∪ { v } and E ′ ⊇ E . Let ( G ′ ) + = ( V ′ , ( E ′ ) + ) denote the transitive closure of G ′ . The decision process modeled as follows:

The Initial Max Hub Score Strategy (Init HS) chooses the vertex with the highest hub score based on the graph prior to the addition of v. The Iterative Max Hub Score Strategy (Iter HS) chooses the vertex with the highest hub score based on the current decision state, i.e. it iteratively considers already existing edges from v. The Initial Reachability Strategy (IRS) chooses the vertex with the highest number of not yet referenced vertices reachable, i.e. reachability, based on the graph prior to the addition of v. The Additional Reachability Strategy (ARS) chooses the vertex with the highest additional reachability based on the current decision state, i.e. it considers vertices already reachable from v.

Given a decision state, each decision strategy determines a set of vertices that it deems best as a potential next reference using its corresponding decision criterion. The set of vertices proposed by each of the decision strategies is referred to as the option set of that strategy given a decision state. Each vertex in the option set is deemed equally well-suited as a next reference; a random vertex from the option is chosen.

9.2.2. Methodology: Experimental analysis

The performance of the decision strategies is assessed by conducting an experimental analysis. Given a probability p that an edge exists between two vertices, a DAG with a fixed number of vertices n is randomly generated. There is no restriction on the graph other than it being a DAG. We examine such graphs with 20, 50 and 100 vertices at an edge probability between 0.95 and 0.05 by steps of 0.05. That is: n ∈ { 20 , 50 , 100 } and p ∈ { 0.95 , 0.90 , 0.85 , … , 0.15 , 0.10 , 0.05 } . For each combination ( n , p ) , 400 random DAGs were generated. All measurement values are averages over those 400 graphs.

An additional vertex v is introduced as the basis for the decision process. Possible11

We evaluate the decision strategies’ performance with two approaches: First, we evaluate the proposed option sets on set-level. We evaluate a strategy’s ability to find all optimal options, i.e. equality comparison. Additionally, we evaluate a strategy’s ability to provide at least one optimal option without proposing a non optimal option, i.e. subset comparison. However, these option set comparisons lack qualitative expressivity regarding how good the option set is compared with the optimal option set as any set with one non-optimal candidate is discarded. Second, we evaluate the proposed option sets on element-level using precision and recall to assess the internal quality of the proposed option set. We evaluate a strategy’s ability to propose all optimal options using recall, and the ability to propose optimal options rather than non-optimal using precision. Precision and recall allow for better understanding of how well a strategy is able to find optimal options as opposed to an optimal (sub-)set.

In dense graphs, the difference in performance between strategies is marginal. In sparse graphs, ARS exhibits significantly better performance than the other strategies. ARS is able to propose option sets with high precision and very high recall. Even when considering subsets or set equality, ARS outperforms the other strategies significantly. Results of the experimental analysis suggest that ARS provides a well-performing heuristic. As an exemplary illustration of the results,12

OPEN IN VIEWER

Fig. 7.

Performance in random graphs with 100 vertices: ARS (red), IRS (green), IterHS (orange), InitHS (blue).

We investigate the influence of document availability, i.e. a varying link structure within the graph, and of document confidentiality, i.e. varying access control, on the behaviour of the authority score distribution: First, only content-based links are created between documents of the same interaction channel (case A1). The link structure is not affected by any access control rules or documents being publicly accessible. Second, we assess the same document graph but now only consider score-based links, i.e. links that have been added to the documents to optimise the trust scores (cases (A2, C1) and (A2, C2)). Here, access control limits the number of available documents for linking. Third, we consider the same document graph but look at both types of links at the same time (cases (A3, C1) and (A3, C2)). Figure 8 summarizes the cases considered for the analysis of the document graph.

OPEN IN VIEWER

Fig. 8.

An overview of examined evaluation cases.

For each of the described cases, a simulation is conducted with a four-phase structure:

Construction of agent network and interaction model.

Using the Watts–Strogatz model [50], we generate an agent network where two types of interaction channels exist: Two-agent-interaction of directly connected agents; and multi-agent-interaction of each agent with all its directly connected agents. Agent interaction is expressed in form of interlinked documents with connections based on the considered simulation case. The result of this phase is an agent network where each agent has access to certain interaction channels.

9.3.3. Simulation parameters

For the simulations, the number of agents is set to 50. In agent network generated by the Watts–Strogatz model, each agent is connected to 4 neighboring agents with a probability of 0.25 that the connection to a neighboring agent is rewired. Regarding the interaction phase, agents are activated in a round with a fixed probability of 0.1. The activation probability was chosen to represent large-scale networks where multiple agents are active simultaneously. An activated agent chooses a interaction channel it publishes a message in with equal probability from all channels available to the particular agent. The interaction phase is completed after 100 agent activation rounds. The deletion of documents based on betweenness centrality is dependent on the created graph. For recovery, the initial effort of all agents to reconnect the graph is fixed. Each agent publishes one new document referencing all documents that are not referenced by other documents. The following extension of the reconnected graph is similar to the interaction phase: Agents are activated with fixed probability of 0.1 and randomly choose an available chat to publish a new message. The extension interaction lasts only 10 rounds as opposed to the creation interaction phase’s 100 rounds. The number of iterations of the Monte Carlo method is set to 1000 to achieve an overall reasonable representation of the documents’ authority score distributions for the four document graphs, i.e. baseline, disconnected, reconnected and extended document graph.

OPEN IN VIEWER

Fig. 9.

Boxplots of authority scores for case (A1) (top-row), case (A2, C1) and (A2, C2) (mid-row) and case (A3, C1) and (A3, C2) (bottom row) for the baseline, disconnected, reconnected and extended graph.

We provide a high-level summary of our results. We visualised the results for all evaluation cases using boxplots depicted in Fig. 9. Note that in case (A1), we observe a drastic change in trust score distribution which is caused by the initial effort of agents to reconnect the graph. More specifically, documents added after that point are able to contribute to more documents’ authority score than previously. This is out-of-the-ordinary for this scenario and thus must be taken with a grain of salt.

In general, the analysis of the document graph shows that the authority scores of documents suffer severely when the graph becomes weakly disconnected. This is reflected by the authority score distribution exhibiting a strong positive skew14

Availability: Comparison of link structures Content-based links produce sparse graphs. Score-base links produce decently connected graphs with quick recovery potential. Having both types of links produces dense graphs that recover more slowly. To achieve disconnection, more documents need to be removed in better connected graphs than in sparse graphs. Similarly, more documents are needed for recovery in better connected graphs than in sparse graphs. This is due to dense graphs being less sensitive to one documents being deleted or added. Since it takes more documents in dense graphs to achieve disconnection, well-connected graphs show a higher sensitivity to disconnection regarding their authority score distribution than sparse graphs. Similarly, recovery takes more added documents in well-connected graphs than in sparse graphs. More documents removed equals more effect on the authority score distribution.

Confidentiality: Access control vs. transparency Transparency allows for very well-connected graphs. This is reflected by strong negative skews in the authority score distribution. Moreover, the authority score distribution is shifted towards higher values when recovering from graph disconnection. This indicates that the graph is connected such that quick recovery is possible. Reaching pre-disconnection levels, however, is not immediate. Confidentiality reduces the connectedness of a graph by fostering clusters of resources. This is reflected by a more spread out authority score distribution. In the conducted simulation, the observed distributions for score-based and both-link-type graphs were fairly balanced only showing a slight positive skew. This indicates that resources under access control may exhibit lower authority scores than with transparency, which is expected. The overall balanced authority score distributions seem reasonable enough to be practically relied on in an application context.