We will use a fairly simple schema inspired by the Social Graphand Interest Graph examples from Jordan [2]. While other labels and properties may exist in the graph, your queries will focus on:

Vertices with a :Person label that have a Name property

Vertices with an :Interest label that have an Interest property

.  Edges between people vertices that have a :Friends label and a Since property; these should not be duplicated

.  Edges between interest vertices that have a :SimilarTo label

Edges from people vertices to interest vertices that have an :InterestedIn label

Query Specifications

You will write functions that evolve the social-interest graph, both in cypher and in python/networkx. The four separate functions/queries should perform the following behaviour:

1. Triadic Closure: Add an edge from every user vertex to every friend of a friend to whom they are not already connected

2. Homophily: Add an edge from every user vertex to every other user vertex with at least two common interests if they are not already connected

3. Rewiring: For each user vertex, remove the edge with the fewest common friends and replace it with an edge to the user vertex within three hops that has the most common interests

4. Interest Similarity: For each interest vertex, add an edge to other interest vertices if at least 50% of user's connected to that vertex are also connected to the target vertex

Triadic Closure

You should insert edges to close altriangles among user vertices in the graph, orienting the new edges from the node with lower id to the node with higher id. As an example, if your graph had only user vertices and had edges {(A, B), (B,C), (C, D)} prior to calling this function, it should have edges {(A, B), (B,C), (C, D), (A,C), (B, D)} afterwards. Observe that this is not recursively applied; e.g., in this example, the triangle (A,C, D) has not been closed.

This represents all friends of friends simultaneously becoming friends. In a software simulation, we would apply some probability to each new edge to add randomness to the graph evolution.

Homophily

You should insert edges to connect alpersons who share at least two common interests, orienting the new edges from the node with lower id to the node with higher id. As an example, if your graph had interest vertices {I0, I1}, person vertices {P1, P2, P3}, and edges {(P0, I0), (P0, I1), (P1, I0), (P2, I0), (P2, I1)} prior to calling this function, it should have edges {(P0, I0), (P0, I1), (P1, I0), (P2, I0), (P2, I1), (P0, P2)} afterwards.

Moreover, if two interests are similar to each other, this should also be considered. For example, if person P0 likes I0, P1 likes I1, and I0 is similar to I1, this implies that P0 and P1 have a similar interest. However, it should not be redundant. In the prior example, if P1 also likes I0, then it doesn't matter that I0 and I1 are similar. Finally, if P0 and P1 both like I0 and I1, but I0 and I1 are similar, then this only counts as one shared interest.

This represents everyone in the graph becoming instantly friends with everyone who is similar to them. Again, in a software simulation, we would apply some probability to each new edge that is added.

Rewiring

You should change one edge for each person, u. Specifically, you should remove the edge incident to u to the person vertex v for which u has the fewest mutual friends. This might be, but is not necessarily, the same edge that should be removed for vertex v. This should be replaced with a new edge for u to the person vertex that is a friend of a friend or a friend of a friend of a friend and has the most mutual interests. For simplicity, in this function, you do not need to consider the similarity between interests, simply the total number of direct connections. Break ties by removing and adding vertices with the lowest id. If the edge to be removed is the same as the edge to be added, then do not remove it.

For example, if P0 is friends with P1 who is friends with P2 and P3 is friends with P4 who is friends with P5 and P0, P2, P3, and P5 all like I0, the the resulting edges would be {(P0, P2), (P1, P2), (P3, P5), (P4, P5), (P0, I0), (P2, I0), (P3, I0), (P5, I0)}.

This represents everyone in the graph ditching their friend least integrated within their social circle and instead befriending somebody (probably) new who has lots of common interests.

Interest Similarity

You should add edges from interest node u to v if at least half of people interested in u are also interested in v. For example, if you have edges {(P0, I0), (P0, I1), (P1, I1), (P2, I1)} prior to the function call, then afterwards you should have edges {(P0, I0), (P0, I1), (P1, I1), (P2, I1), (I0, I1)}.

This represents a batch update to the graph for making recommendations using an extreme simplification of collaborative filtering.

Submission

You should submit the attached python file and four cypher files, having completed the empty functions or empty queries. Do not rename the files or the grading script will not discover them.

Grading

The four cypher queries and the four python/networkx functions will all be graded with a script set up with five unit tests each. The unit tests will match between cypher and python/networkx. Your score on the assignment will be the number of unit tests that you pass. Grading will take place periodically until the deadline and you will receive the last grade assigned. Thus, it is possible to submit your assignment repeatedly up until the deadline and receive preliminary grades that indicate your progress so far.

Sources and Academic Integrity

You are permitted to use sources that you find on the Internet, so long as the source is clearly dated with a last edit prior to 1-January-2023 and you provide a citation in your source code. For example, GitHub and StackOverflow content is permitted, so long as their last edit date is clearly dated prior to this year. If you do not include a citation in your source code, your work will be considered plagiarism.