Given a complicated graphs, say social networks, what properties/quantity people want to know about them?
In geo/rideshare/logistics: shortest-path routing, traffic flow, minimizing the distance driven by someone who needs to make multiple pickups, optimizing delivery routes.
In health: contact tracing, recommending closures of social activities
In industrial/EE applications: circuit theory, flow networks, load stresses
In basic CS infrastructure: register allocation, dependency management, dead code removal, data-flow propagation, figuring out bandwidth requirements in a network
Design a data structure that represents "business logic" as a graph and transformations between graphs.
Now given two distinct "business logic" data structures, A and B, write an algorithm that can:
- check if all flows/paths through A are present in B
- if not, enumerate which paths are no longer present
- for each path not present in B that is in A, enumerate possible substitutions
- for any given path in A and B define a distance metric that estimates the cost of any flow in A versus in B
Now I haven't don't this so I don't know if there's an elegant way to do it without some serious category theory/abstract algebra chops, but this is essentially a problem that costs millions of dollars in businesses. Evaluating changes to processes and their potential cost/benefit as well as deltas to other processes when structures are changed is extremely expensive, and it's why migrating ERPs or CRMs is so time consuming.
Of course for it to be real world, you need the business logic to be fuzzy because you don't have all the information to define such graphs A and B perfectly.
I think there are a number of ways to state this problem in terms of graphs and their transformations, that's usually the case when it comes to abstractions. I think the question more worth answering is the methods by which real world organizational and business problems/processes can be expressed as graphs and their transformations, and how to perform analysis of those graphs for given queries about their nature.
I know a few people who do this but not as a rigorous CS discipline, it's often called Industrial Organizational Psychology, Process Optimization, etc etc. Its a complex interdisciplinary field.
But to take an example from my visual planning - Gameplan.global - i use graph algorithms to model task dependencies, as well as the grouping structure.
When the tasks and dependencies are modelled as a graph, and the user wants to change a dependency, I can check the graph for a cycle. If a cycle will be introduced after the change, the change is disallowed.
It's not as grandiose as one could imagine for a very large social network graph, its practical and solved the problem I.
"Search" here means subgraph isomorphism search.
No one that I know of uses a graph isomorphism test to compare two structures. Instead, they convert the molecular graph into a string, where the atoms and bonds are in a canonical order - perhaps a SMILES string or InChI string - and use a string search. Graph canonicalization is therefore important for molecular search, but not for the "complicated graphs, say social networks" the OP mentioned.
One specialized topic I worked on was the maximum common substructure problem. Given two molecules, what is the largest subgraph. Now extend that to N molecules. Now, find the largest subgraph which is in at least P% of those molecules.
For the rest? No. I'm primarily a software developer, not paper author.
There's my co-authored paper at https://pubs.acs.org/doi/10.1021/acs.jcim.8b00173 , which depends a lot on (sub)graph canonicalization.
The maximum common substructure algorithm I developed, for a set of compounds, is part of the RDKit, "fmcs". The original pure-Python implementation is at https://bitbucket.org/dalke/fmcs/src . It's been rewritten since then in C++ for the RDKit.
The Python code is easier to understand.