Graph-Based Social Network Analysis
Project: A Graph-Based Social Network Analysis Tool
Objective:
The task is to design and implement a program that analyzes a social network represented as a graph. The program should allow users to input the graph, specify query parameters, and retrieve meaningful insights about the network.
Graph Representation:
The social network will be represented as an adjacency list or adjacency matrix, where each node represents a person, organization, or entity, and edges represent relationships between them (e.g., friendships, followers, collaborations).
Functional Requirements:
- Node Information Retrieval: Write a function that takes a node ID as input and returns the node’s attributes (e.g., name, age, profession).
- Edge Traversal: Implement an algorithm to traverse the graph, starting from a given node, and retrieve all nodes reachable within a specified distance (e.g., 1-3 hops).
- Community Detection: Use a clustering algorithm (e.g., k-means, DBSCAN) to identify communities within the network based on edge connections.
- Centrality Measures: Calculate various centrality measures (e.g., degree, closeness, betweenness) for each node in the graph.
- Querying: Develop an interface that allows users to input queries and retrieve relevant information about the social network. Examples of queries:
- Find all nodes connected to a given node within a specific distance.
- Identify the most central nodes in the network.
- Retrieve the community structure of the network.
Non-Functional Requirements:
- Efficiency: The program should be able to handle large-scale social networks efficiently, with acceptable running times and memory usage.
- Usability: The user interface should be intuitive, allowing users to easily input queries and retrieve results.
- Error Handling: Implement robust error handling for invalid inputs or unexpected graph structures.
Deliverables:
- A written report (5-7 pages) that:
- Describes the graph representation and algorithms used.
- Discusses the functional and non-functional requirements.
- Presents any challenges encountered during implementation and how they were addressed.
- A working program (Python, Java, or C++) with a user-friendly interface that demonstrates the above features.
Evaluation Criteria:
- Correctness of implemented algorithms and data structures.
- Efficiency and scalability of the program.
- Usability and intuitiveness of the user interface.
- Clarity and organization of the written report.
- Creativity and originality in approach to problem-solving.